Лабораторная работа № 2 "Численное решение систем линейных алгебраических уравнений"

Данная лабораторная работа посвящена нахождению корней систем линейных алгебраических уравнений. Методы численного решения таких систем подразделяются на два типа: прямые (конечные) и итерационные (бесконечные). Оба типа полезны и удобны для практических вычислений и каждый из них имеет свои преимущества и недостатки.

1. Метод исключения (метод Гаусса)

- наиболее известный и широко применяемый прямой метод решения.

Рассмотрим систему из n уравнений с n неизвестными. Обозначим неизвестные через х₁, х₂, … , х_n и запишем систему в следующем виде:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁ (1)

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n = b₂

… … … … … … … … …

a_n1x₁ + a_n2x₂ + … + a_nnx_n = b_n

Предполагается, что в силу расположения уравнений, а_n0. Если это не так, то, меняя уравнения местами, добиваемся выполнения этого условия. Введем n-1 множителей

m_i = a_i1/a₁₁,

i = 2, 3, … , n

и вычтем из каждого i - го уравнения первое, умноженное на m_i, обозначая

a'_ij = a_ij – m_ia_1j,

b'_i = b_i – m_ib₁,

i = 2, 3, … , n,

j = 1, 2, 3, … , n.

Для всех уравнений, начиная со второго,

a'_i = 0, i = 2, 3, … , n.

Преобразованная система уравнений запишется в следующем виде

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁

0 + a'₂₂x₂ + … + a'_2nx_n = b'₂

… … … … … … … … …

0 + a'_n2x₂ + … + a'_nnx_n = b'_n

Продолжая таким же образом, исключаем х₂ из последних n-2 уравнений, затем х₃ из последних n-3 и т.д. На некотором k-м этапе мы исключаем х_k с помощью множителей

m_i^(k-1) = a_ik^(k-1) / a_kk^(k-1), i = k+1, … , n, (2)

причем предполагается, что a_kk^(k-1)0.

Тогда

a_ij^(k) = a_ij^(k-1) – m_i^(k-1) a_kj^(k-1), (3)

b_i^(k) = b_i^(k-1) – m_i^(k-1) a_k^(k-1),

i = k+1, … , n,

j = k, … , n.

Окончательно треугольная система уравнений записывается:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁ (4)

a'₂₂x₂ + … + a'_2nx_n = b'₂

… … … … … … … … …

a_nn^(n-1)x_n = b_n^(n-1)

Обратная подстановка для нахождения значений неизвестных задается формулами:

x_n = b_n^(n-1) / a_nn^(n-1) (5)

x_n-1 = (b_n-1^(n-2) - a_n-1,n^(n-2)x_n) / a_n-1,n-1^(n-2)

… … … … … … … … … … … …

x_j = (b_j^(j-1) – a_j,n^(j-1)x_n - … - a_j,j+1^(j-1)x_j+1) / a_j,j^(j-1)

j = n-2, n-3, … , 1.

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

|a_kk^(k-1)||a_ik^(k-1)|. (6)

Поэтому перед началом процесса исключения очередного неизвестного необходимо переставить n-k+1 уравнений так, чтобы максимальный по модулю коэффициент при х_k попал на главную диагональ (данный способ решения часто называется методом главного элемента).

2. Итерационный метод Гаусса-Зейделя

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

Рассмотрим систему (1) из n уравнений с n неизвестными. По-прежнему полагаем, что a_ii0 для всех i. Тогда k-е приближение к решению будет задаваться формулой:

x_i^(k) = (1/a_n)(b_i – a_i1x₁^(k) - … - a_i,i-1x_i-1^(k) - a_i,i+1x_i+1^(k-1) - … - a_i,nx_n^(k-1)) (7)

Итерационный процесс продолжается до тех пор, пока все х_i^(k) не станут достаточно близки к х_i^(k-1), т.е. пока для всех i не будет выполняться неравенство

max|x_i^(k) - x_i^(k-1)|< (8)

где некоторое положительное число.

Итерационный метод Гаусса-Зейделя сходится, если удовлетворяется достаточное условие сходимости: для всех i модуль диагонального коэффициента должен быть не меньше суммы модулей остальных коэффициентов данной строки

|a_ii||a_i,1|+| a_i,2|+…+| a_i,i-1|+| a_i,i+1|+…| a_i,n|, (9)

а хотя бы для одной строки это неравенство должно выполняться строго

|a_ii|>|a_i,1|+| a_i,2|+…+| a_i,i-1|+| a_i,i+1|+…| a_i,n|. (10)

Выполнение данной лабораторной работы заключается в решении системы линейных алгебраических уравнений 4-го порядка перечисленными выше методами. Коэффициенты a_ij и свободнее члены b_i заданы в таблице.

Отчет по лабораторной работе должен содержать:

1. Исходную систему уравнений.

2. Текст программы и пошаговые результаты расчета искомых корней методом исключения.

3. Текст программы и пошаговые результаты расчета искомых корней итерационным методом Гаусса-Зейделя. Начальное приближение для всех х_i⁽⁰⁾ = 0. Точность вычисления корней = 0,001. (Решение системы осуществляется при выполнении достаточного условия сходимости!).

4. Выводы, содержащие проверку найденного решения и анализ точности и сходимости рассмотренных методов.

Таблица 1. Исходные данные для лабораторной работы №2

Вар.	ai1	ai2	ai3	ai4	bi
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25	16 -9 6 -9 -1 24 -8 -3 5 -5 8 -8 -7 -14 6 -9 -23 -5 -9 -3 -8 -18 -3 7 -8 4 15 -4 5 5 -16 -8 -13 -3 8 -7 19 9 7 9 1 -3 -4 18 20 -2 3 -1 5 9 -14 2 -6 -5 -22 8 2 3 -5 15 9 2 17 6 -1 -13 9 4 23 8 5 -7 -5 -20 -2 -4 -5 28 -7 7 -5 19 -7 4 4 3 8 -23 20 -1 9 -5 -8 8 17 -6 7 -7 -8 20	5 7 15 -7 -3 -8 -4 -11 1 -5 -2 18 -2 -4 1 21 3 8 -6 -7 -28 2 -5 -8 2 -22 3 -4 -9 -19 -3 9 2 3 19 9 -6 8 6 22 -14 1 -5 2 2 21 -5 4 -1 -29 -3 6 11 -5 -6 2 20 -8 -9 3 5 -11 8 -1 -9 6 -6 1 3 -23 9 1 -2 9 13 8 14 7 -5 1 -4 2 -22 -7 2 7 -3 9 -5 22 6 -6 -1 -3 8 -15 5 -26 -3 6	1 8 4 23 -12 6 1 3 16 -6 -3 -1 23 -3 -7 -9 7 1 29 2 -3 -7 -16 -4 17 6 -5 5 -21 -8 -4 8 3 -15 -5 -9 -2 2 22 -3 2 -3 19 6 6 8 2 21 14 7 -8 -4 -1 19 -4 -8 9 23 -3 -5 3 -1 -4 13 -2 4 23 2 -8 -8 5 -22 1 -2 -7 27 -2 9 2 -12 2 6 6 -20 12 -1 6 -5 6 7 24 -8 7 -16 3 -2 -17 8 -3 4	-8 -28 -3 -4 -7 8 14 -3 -5 17 1 -7 8 6 16 -2 8 1 9 -14 8 5 3 -20 -5 5 -5 14 -6 5 -8 31 -7 7 -4 -31 5 23 6 8 -5 -15 -9 8 -6 -7 -13 -8 4 -9 1 -14 -2 -7 8 -19 8 -6 -19 5 21 -7 2 -5 5 -1 -6 -8 -4 -5 24 8 12 2 3 -7 4 -9 -16 3 17 6 6 5 1 1 20 8 -5 8 -2 22 -20 2 3 -6 -3 -7 -20 6	189.50 230.93 132.27 -2.51 62.40 -66.00 -116.40 -109.72 -72.32 131.04 -13.10 -70.46 1.90 85.67 -190.31 -73.66 152.53 37.77 -129.99 -125.52 -39.63 -207.40 -153.12 52.91 -119.97 55.73 18.77 -79.42 142.45 97.62 -19.68 -242.09 74.11 175.65 84.46 193.31 43.52 -42.08 12.83 18.60 136.79 70.19 237.83 80.32 -103.72 204.10 -97.58 45.76 152.09 132.51 -189.84 -24.46 88.86 -207.99 88.26 -82.35 9.05 -203.55 -164.79 159.67 129.18 -58.91 89.35 -38.81 -35.03 -66.26 -115.25 50.17 -107.40 -39.42 111.33 323.10 33.25 42.62 -53.19 52.41 -8.63 -190.09 156.35 -87.97 5.42 31.80 6.48 -17.68 45.26 90.90 102.39 -123.98 -55.11 88.84 84.63 -134.11 -100.20 183.18 30.28 83.42 62.22 -92.42 -7.52 -68.80