Пример: Глобальная сеть INTERNET
Я ищу:
На главную  |  Добавить в избранное  

Главная/

Программирование, базы данных. /

Решение систем линейных алгебраических уровнений методоми Гаусса и Зейделя

←предыдущая следующая→
1 2 3 4 5 

ведущий) элемент k-го шага akk(k–1) отличен от нуля, вычислим множители k-го шага

qik = aik(k–1) / akk(k–1)   (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на qk+1,k, qk+2,k, …, qnk.

После (n - 1)-го шага исключения получим систему уравнений

            a11x1 + a12x2 +      a13x3 +   … +  a1nxn =        b1        ,

                        a22(1)x2 +   a23(1)x3 +          … +            a2n(1)xn =            b2(1)        ,

                                        a33(2)x3 +          … +            a3n(2)xn =            b3(2)        ,

            .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

                                                                ann(n–1)xn =   bn(n–1) .

матрица A(n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение xn в предпоследнее уравнение, получим xn–1. Осуществляя обратную подстановку, далее последовательно находим xn–1, xn–2, …, x1. Вычисления неизвестных здесь проводятся по формулам

xn = bn(n–1) / ann(n–1),

xk = (bn(k–1) – ak,k+1(k–1)xk+1 – … – akn(k–1)xn) / akk(k–1), (k = n – 1, …, 1).

Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы akk(k–1). Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

1.1.2. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k-м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам

aij(k) = aij(k–1) − qikakj , bi(k) = bi(k–1) − qikbk(k–1) , i = k + 1, …, n.

Интуитивно ясно, что во избежание сильного роста коэффициентов системы и связанных с этим ошибок нельзя допускать появления больших множителей qik.

В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |qik| ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент aikk при неизвестной xk в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером ik меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента akk(k-1). После этой перестановки исключение неизвестного xk производят, как в схеме единственного деления.

1.1.3. Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора). В этой схеме допускается нарушение естественного порядка исключения неизвестных.

На 1-м шаге мтода среди элементов aij определяют максимальный по модулю элемент ai1j1. Первое уравнение системы и уравнение с номером i1 меняют местами. Далее стандартным образом производят исключение неизвестного xi1 из всех уравнений, кроме первого.

На k-м шаге метода среди коэффициентов aij(k–1) при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент aikjk(k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное xjk из уравнений с номерами i = k + 1, …, n.

На этапе обратного хода неизвестные вычисляют в следующем порядке: xjn, xjn–1, …, xj1.

1.2. Метод Зейделя

1.2.1. Приведение системы к виду, удобному для итераций. Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений

Ax = b

с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду

                x = Bx + c.

Здесь B – квадратная матрица с элементами bij (i, j = 1, 2, …, n), c – вектор-столбец с элементами cij (i = 1, 2, …, n).

            В развернутой форме записи система имеет следующий вид:

            x1 = b11x1 + b12x2 + b13x3 + … + b1nxn + c1

            x2 = b21x1 + b22x2 + b23x3 + … + b2nxn + c2

            .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

            xn = bn1x1 + bn2x2 + bn3x3 + … + bnnxn + cn

 

            Вообще говоря, операция приведения системы к виду, удобному для итераций, не является простой и требует специальных знаний, а также существенного использования специфики системы.

            Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x1:

            x1 = a11–1 (b1 – a12x2 – a13x3 – … – a1nxn),

из второго уравнения – неизвестное x2:

            x2 = a21–1 (b2 – a22x2 – a23x3 – … – a2nxn),

и т. д. В результате получим систему

            x1 =               b12x2 +   b13x3 + … +  b1,n–1xn–1 +  b1nxn+  c1 ,

            x2 = b21x1 +                 b23x3 + … +  b2,n–1xn–1 +  b2nxn+  c2 ,

            x3 = b31x1 +   b32x2 +               … +  b3,n–1xn–1 +  b3nxn+  c3 ,

            .   .   .   .  

←предыдущая следующая→
1 2 3 4 5 


Copyright © 2005—2007 «RefStore.Ru»