Métodos iterativos
1
1
Introdu¸˜o ca Um Sistema Linear pode ser definido como um conjunto finito de equa¸˜es co que satisfazem-se simultaneamente. Sua forma ´ ilustrada a seguir: e a11 x1 + a12 x2 + a13 x3 + ... + a1n xn = b1 a21 x1 + a22 x2 + a23 x3 + ... + a2n xn = b2
.
.
.
am1 x1 + am2 x2 + am3 x3 + ... + amn xn = bm
O sistema acima ´ constitu´ de m equa¸oes de n inc´gnitas. e ıdo c˜ o
O objetivo deste trabalho ´ implementar diferentes algoritmos para soe lucionar sistemas lineares. Os algoritmos a serem implementados s˜o os a seguintes:
• Decomposi¸ao LU (Lower / Up); c˜ • M´todo de Cholesky e • M´todo de Jacobi e • M´todo de Gauss-Seidel e 2
2
Decomposi¸˜o LU ca O met´do de Decomposi¸˜o LU consiste em diminuir o custo computao ca cional ao resolver um sistema de equa¸oes lineares. O primeiro passo a se c˜ tomar ´ verificar se ´ poss´ aplicar a decomposi¸˜o em determinado sise e ıvel ca tema. Para isso ´ necess´rio verificar que o determinante de toda sub-matriz e a
Ai de A, com i variando de 1 at´ n-1 seja diferente de 0. Se esta condi¸ao se e c˜ satisfazer, ent˜o ´ poss´ decompor a matriz A em duas matrizes L e U. ae ıvel
A matriz L possu´ os elementos da diagonal principal iguais a 1, e acima ı da diagonal principal, todos os elementos nulos. J´ a matriz U possui apenas a os elementos abaixo de sua diagonal principal nulos. O restante dos elementos
´ poss´ calcular da seguinte maneira: e ıvel
A primeira linha de U ´ calculada, em seguida a primeira coluna de L, e depois a segunda linha de U, em seguida segunda coluna de L, e assim sucessivamente at´ todos os elementos serem calculados. Para calcular cada e elemento as seguintes f´rmulas s˜o usadas: o a
Figura 1: Fun¸ao para calcular elementos de U c˜ Figura 2: Fun¸ao para calcular elementos de L c˜ Assim o sistema Ax = b pode ser escrito como LUx = b,