Вычислительная математика Решение систем линейных алгебраических уравнений. - презентация

1 Вычислительная математика Решение систем линейных алгебраических уравнений

2 Краткие теоретические сведения Пусть имеется система линейных уравнений a 11 x 1 +a 12 x 2 +…+a 1n x n =d 1, a 21 x 1 +a 22 x 2 +…+a 2n x n =d 2, (1) a n1 x 1 +a n2 x 2 +…+a nn x n =d n. Систему (1) можно записать в матричном виде Ax=d. (2) Здесь А – матрица коэффициентов левых частей системы (1), а x и d – два n-мерных вектора

3 Метод Гаусса Метод Гаусса, или метод последовательного исключения неизвестных состоит из двух этапов: прямого хода и обратной подстановки. При прямом ходе система приводится к специальному – треугольному – виду, либо выясняется, что она несовместна или имеет бесконечно много решений. Прямой ход выполняется как последовательность шагов, их не более n–1, где n – порядок системы. Задача каждого шага – исключение из системы очередного неизвестного. Предположим, что в системе (1) коэффициент a 11 не равен нулю. Если бы это было не так, но зато a10, то мы поменяли бы местами 1-е и -е уравнения. Составим отношения i1 =, i=2, 3, …, n, называемые множителями 1-го шага; коэффициент a 11 при этом называется главным элементом 1-го шага. Умножая 1-е уравнение соответственно на 21, 31, …, n1, вычтем его из 2-го, 3-го,...., n-го.

4 Метод Гаусса В результате придем к системе вида a 11 x 1 +a 12 x 2 +…+ a 1n x n =d 1, a 22 (1) x 2 +…+a 2n (1) x n =d 2 (1), ……………………………… a n2 (1) x 2 +…+a nn (1) x n =d n (1), имеющей те же решения, что и система (1) Коэффициенты новой системы вычисляются по формулам: a ij (1) =a ij - i1 a 1j, i, j=2, 3, …, n, (3) d i (1) =d i - i1 d i, i=2, 3, …, n. Первый шаг прямого хода закончен. Уравнения со 2-го по n-е составляют систему порядка n–1, в которой нет неизвестного xоно исключено, с чем и связано одно из названий метода.

5 Метод Гаусса Может случиться, что в новой системе появилось уравнение, в котором все коэффициенты левой части равны нулю. Если правая часть такого уравнения ненулевая, то система, очевидно, несовместна. Если же и правая часть равна нулю, то такое уравнение можно удалить из системы; в результате число уравнений станет меньше n. Если несовместных уравнений в системе нет, то можно перейти ко второму шагу. Будем считать, что коэффициент a 22 (1)0; в противном случае мы переставили бы 2-е уравнение с одним из нижележащих, именно с тем, в котором присутствует x 2.

6 Метод Гаусса Составляем множители 2-го шага: i2 =a i2 (1) /a 22 (1), i=3, 4, …, n. Коэффициент a 22 (1) называется главным элементом второго шага. Вычитая из 3-го, 4-го,..., n-го уравнений 2-е, умноженное соответственно на 32, 42,…, n2, получим a 11 x 1 +a 12 x 2 +a 13 x 3 +…+ a 1n x n =d 1, a 22 (1) x 2 +a 23 (1) x 3 +…+a 2n (1) x n =d 2 (1), a 33 (2) x 3 +…+a 3n (2) x n =d 3 (2), ……………………………… a n3 (2) x 3 +…+a nn (2) x n =d n (2). Для коэффициентов справедливы соотношения, аналогичные формулам (3): a ij (2) =a ij - i2 a 1j, i, j=3, 4, …, n, (4) d i (2) =d i (1) - i2 d i (1), i=3, 4, …, n.

7 Уравнения новой системы, кроме первых двух, составляют систему порядка n–2, в которой нет неизвестных x 1 и x 2 ; неизвестное x 2 исключено на втором шаге. Продолжая таким образом, мы или установим, что система несовместна, или после исключения k-гo неизвестного (1

8 Коэффициенты a 11, a 22 (1),…, a n-1,n-1 (n-2), будучи главными элементами соответствующих шагов, не равны нулю согласно определению. Для невырожденной матрицы А не равен нулю и коэффициент a nn (n-1). Обратной подстановкой называется следующий этап – решение треугольной системы (5). Из последнего уравнения делением на a nn (n-1) получаем значение неизвестного x n. Подставляя его в (n–1)-е уравнение, можем определить значение x n-1. Поднимаясь таким образом по системе, последовательно найдем значения всех неизвестных.

9 Метод Гаусса с выбором главного элемента В методе Гаусса с выбором главного элемента среди элементов a mk (k) mk находят главный, то есть наибольший по модулю в k-м столбце и перестановкой строк переводят его на главную диагональ, после чего делают исключения. Такая схема метода Гаусса позволяет уменьшить погрешность округления. Метод Гаусса с выбором главного элемента надежен и прост. Погрешность округления можно уменьшить, если выбирать в каждом цикле элемент, наибольший по модулю во всей матрице. Однако точность при этом возрастает не сильно по сравнению со случаем выбора главного элемента, а расчет заметно усложняется, так как требует не только перестановки строк, но и столбцов.