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

a ₁₁ x ₁ + a ₁₂ x ₂ + a ₁₃ x ₃ + … + a _1n x_n = b ₁ ,

a ₂₂ ⁽¹⁾ x ₂ + a ₂₃ ⁽¹⁾ x ₃ + … + a _2n ⁽¹⁾ = b ₂ ⁽¹⁾ ,

a ₃₃ ⁽²⁾ x ₃ + … + a _3n ⁽²⁾ x_n = b ₃ ⁽²⁾ ,

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

a_{n 3} ⁽²⁾ x ₃ + … + a_nn ⁽²⁾ x_n = b_n ⁽²⁾ .

Здесь коэффициенты a_ij ⁽²⁾ и b_ij ⁽²⁾ вычисляются по формулам

a_ij ⁽²⁾ = a_ij ⁽¹⁾ – q_{i 2} a _2j ⁽¹⁾ , b_i ⁽²⁾ = b_i ⁽¹⁾ – q_{i 2} b ₂ ⁽¹⁾ .

Аналогично проводятся остальные шаги. Опишем очередной k- й шаг.

k- й шаг. В предположении, что главный (ведущий ) элемент k- го шага a_kk ^{(k –1)} отличен от нуля, вычислим множители k-го шага

q_ik = a_ik ^{(k –1)} / a_kk ^{(k –1)} (i = k + 1, …, n )

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

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

a ₁₁ x ₁ + a ₁₂ x ₂ + a ₁₃ x ₃ + … + a _1n x_n = b ₁ ,

a ₂₂ ⁽¹⁾ x ₂ + a ₂₃ ⁽¹⁾ x ₃ + … + a _2n ⁽¹⁾ x_n = b ₂ ⁽¹⁾ ,

a ₃₃ ⁽²⁾ x ₃ + … + a _3n ⁽²⁾ x_n = b ₃ ⁽²⁾ ,

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

a_nn ^{(n –1)} x_n = b_n ^{(n –1)} .

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

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

x_n = b_n ^{(n –1)} / a_nn ^{(n –1)} ,

x_k = (b_n ^{(k –1)} – a_{k ,k +1} ^{(k –1)} x_{k +1} – … – a_kn ^{(k –1)} x_n ) / a_kk ^{(k –1)} , (k = n – 1, …, 1).

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

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

a_ij ^{(k )} = a_ij ^{(k –1)} − q_ik a_kj , b_i ^{(k )} = b_i ^{(k –1)} − q_ik b_k ^{(k –1)} , i = k + 1, …, n .

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

В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |q_ik | ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n . Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k -м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент a_ikk при неизвестной x_k в уравнениях с номерами i = k + 1, …, n . Затем соответствующее выбранному коэффициенту уравнение с номером i_k меняют местами с k -м уравнением системы для того, чтобы главный элемент занял место коэффициента a_kk ^{(k -1)} . После этой перестановки исключение неизвестного x_k производят, как в схеме единственного деления.

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

На 1-м шаге мтода среди элементов a_ij определяют максимальный по модулю элемент a_{i 1j 1} . Первое уравнение системы и уравнение с номером i ₁ меняют местами. Далее стандартным образом производят исключение неизвестного x_{i 1} из всех уравнений, кроме первого.

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