Additive Schwarz method: Difference between revisions

Revision as of 14:09, 19 June 2005

Revision as of 03:07, 21 June 2005

Line 1:

In mathematics, [[numerical analysis]] and numerical [[partial differential equation]]s, the '''___domain decomposition method''' solves a [[boundary value problem]] by splitting it into smaller boundary value problems.

== Overview ==

Partial differential equations (PDEs) are used in all hard sciences[[science]]s to [[mathematical modelling|model]] phenomena. For the purpose of exposition, we give an example physical problem and the accompanying boundary value problem (BVP). Even if the reader is unfamiliar with the notation, the purpose is merely to show what a BVP looks like when written down.

:'''(Model Problem)''' The heat distribution in a square metal plate such that the left edge is kept at 1 degree, and the other edges are kept at 0 degree, after letting it sit for a long period of time satisfies the following boundary value problem:

:'''(Model Problemproblem)''' The heat distribution in a square metal plate such that the left edge is kept at 1 degree, and the other edges are kept at 0 degree, after letting it sit for a long period of time satisfies the following boundary value problem:

::''f''_''xx''(''x'',''y'') + ''f''_''yy''(''x'',''y'') = 0

::''f''(0,''y'') = 1; ''f''(''x'',0) = ''f''(''x'',1) = ''f''(1,''y'') = 0

:where ''f'' is the unknown [[function (mathematics)|function]], ''f''_''xx'' and ''f''_''yy'' denote the second [[partial derivative]]s with respect to ''x'' and ''y'', respectively.

Here, the ''[[___domain'' (mathematics)|___domain]] is the square [0,1] × [0,1].

This particular problem can be solved exactly on paper, so there is no need for a computer. However, this is an exceptional case, and most BVPs cannot be solved exactly. The only possibility is to use a computer to find an approximate solution.

Line 19 ⟶ 18:

=== Solving on a computer ===

A typical way of doing this is to ''sample'' ''f'' at regular intervals[[interval]]s in the [[square]] [0,1] × [0,1]. For instance, we could take 8 samples in the ''x'' direction at ''x'' = 0.1, 0.2, ..., 0.8 and 0.9, and 8 samples in the ''y'' direction at similar [[coordinate system|coordinates]]. We would then have 64 samples of the square, at places like (0.2,0.8) and (0.6,0.6). The goal of the [[computer program]] would be to calculate the value of ''f'' at those 64 points, which seems easier than finding an abstract function of the square.

There are some difficulties, for instance it isn'tis not possible to calculate ''f''_''xx''(0.5,0.5) knowing ''f'' at only 64 points in the square. To solveovercome this, one uses some sort of numerical approximation of the derivatives, see for instance the [[finite element method]] or [[finite difference]]s. We ignore these difficulties and concentrate on another aspect of the problem.

=== Solving linear problems ===

Whichever method we choose to solve this problem, we will need to solve a large [[linear system of equations]]. The reader will recall linear systems of equations from highschool, they look like this:

:2''a'' + 5''b'' = 12 (*)