Курсовая работа: Численное решение системы линейных уравнений с помощью метода исключения Гаусса с выбором главного элемента по столбцу

2-й шаг. Целью этого шага является исключение неизвестного x2 из уравнений с номерами i = 3, 4, …, n. Пусть a22(1) ≠ 0, где a22(1) – коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага

qi2 = ai2(1) / a22(1) (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q32, q42, …, qm2.

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

a11x1 + a12x2 + a13x3 + a1nxn =b1,

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

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

an3(2)x3 + ann(2)xn = bn(2)

Здесь коэффициенты aij(2) и bij(2) вычисляются по формулам

aij(2) = aij(1) – qi2a2j(1) ,bi(2) = bi(1) – qi2b2(1).

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

k-й шаг. В предположении, что главный (ведущий) элемент 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) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

2.1.2 Обратный ход

Обратный ход. Из последнего уравнения системы находим 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). Поэтому если один из главных элементов оказывается равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

2.2 Метод Гаусса с выбором главного элемента по столбцу

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

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