Численные методы линейной алгебры.

Лекция 3: Численные методы линейной алгебры. К численным методам линейной алгебры относятся численные методы решения систем линейных алгебраических уравнений, обращение матриц, вычисление определителей, нахождение собственных значений и собственных векторов матриц. Численные методы решения систем линейных алгебраических уравнений разделяются на две группы: Точные или прямые методы, которые позволяют найти решение системы линейных алгебраических уравнений за конечное число арифметических действий. Сюда относятся метод Крамера (нахождение решения систем с помощью определителей), метод Гаусса, метод прогонки. Приближенные методы. В частности итерационные методы решения систем алгебраических уравнений. Правило Крамера в вычислительной математике с использованием ЭВМ не применяется, т.к. оно требует использования большого числа операций и объемов памяти. Метод Гаусса используется для решения СЛАУ размерности 3. 10 6 10 Итерационными методами решаются системы размерностью . Методом прогонки решаются системы линейных алгебраических уравнений специального вида, содержащие трехдиагональные матрицы. П.1 Метод простой итерации. Рассмотрим систему линейных алгебраических уравнений n – го порядка, записанную в виде: (3.1) B - квадратичная числовая матрица n – порядка. где x x = Bx + b , - n – мерный вектор, неизвестная величина, которую требуется найти. b - n – мерный вектор (известный, заданный столбец свободных членов). Задав x0 ∈ Rn начальное приближение, итерационный процесс нахождения приближенного решения (3.1) сформулируем следующим образом: (3.2) x k = Bx k −1 + b, k = 1,2,... Выясним, при каких условиях на матрицу B, решение найденное по методу простой итерации будет сходиться к решению задачи (3.1). Практическая схема решения СЛАУ методом простой итерации Рассмотрим для простоты систему, состоящую из трёх уравнений с тремя неизвестными: a11 x1 + a12 x2 + a13 x3 = b1 a21 x1 + a22 x2 + a23 x3 = b2 a31 x1 + a32 x2 + a33 x3 = b3 1). Преобразуем эту систему к системе вида: (3.3) ′ x1 + a12 ′ x2 + a13 ′ x3 − b1 = 0 a11 ′ x1 + a22 ′ x2 + a23 ′ x3 − b2 = 0 a21 ′ x1 + a32 ′ x2 + a33 ′ x3 − b3 = 0 a31 где ′ > a12 ′ + a13 ′ a11 (3.4) ′ > a′21 + a′23 a22 ′ > a31 ′ + a32 ′ a33 Этого можно добиться: 1) переставляя столбцы исходной системы; 2) меняя строки; 3) делая линейную комбинацию из строк. 2) из первого уравнения (3.3) выразим x1 ; из второго уравнения (3.3) выразим x2 ; из третьего уравнения (3.3) выразим x3 ; Получим: x1 = c12 x2 + c13 x3 + d1 x2 = c21 x1 + c23 x3 + d 2 x3 = c31 x1 + c32 x2 + d3 Правая часть этой системы имеет нормальную матрицу  0 c12  C =  c21 0 c  31 c32 c13   c23  0   d1    d =  d2  d   3 C = max{ c12 + c13 , c21 + c23 , c31 + c32 } ( x* = x1*, x2*, x3* ) Учитывая (3.4) и обозначив через – точное решение, а через x ( n ) = x ( n ) , x ( n ) , x ( n ) – n – тую итерацию, будем иметь ( 1 2 3 ) n +1 x* − x ( n ) C d ≤ 1− C Найдя C с помощью вышеуказанного равенства, а также d , выясним при N +1 каком номере N будет выполняться неравенство: Метод нахождения xn на n – й итерации имеет вид: C d ≤ε 1− C x1( n ) = c12 x2( n−1) + c13 x3( n−1) + d1 x2( n ) = c21 x1( n−1) + c23 x3( n−1) + d 2 x3( n ) = c31 x1( n−1) + c32 x2( n−1) + d3 В процессе выполнения этого итерационного процесса, на каждом шаге находим разность x ( n ) − x ( n−1) . Когда x (n) −x ( n −1) 1− C ≤ ⋅ε C выполнение итерационного процесса прекращаем, решение найдено с заданной точностью. 3) На практике часто используется итерационный процесс Гаусса – Зейделя, который имеет вид: (3.5) x1( n ) = c12 x2( n−1) + c13 x3( n−1) + d1 x2( n ) = c21 x1( n ) + c23 x3( n−1) + d 2 x3( n ) = c31 x1( n ) + c32 x2( n ) + d 3 Выясним при каких условиях сходится метод Гаусса – Зейделя. Теорема 3.1 3.1:: Для того, чтобы решение по методу Гаусса – Зейделя существовало и было единственно, и для того, чтобы итерационный процесс (3.5) сходился, достаточно выполнение условий (3.4). Литература Е.А. Волков Численные методы, М. Наука, 1987 (либо последующие издания): & 4-12, 15, 19-22, 24,25, 29-33.