Численные методы. Корнюшин П.Н. - 51 стр.

                                                        51


        Численные методы решения системы (1) условно разбивают на две группы, выделяя
прямые и итерационные методы (имеются, естественно, и гибридные методы). Прямые методы
позволяют за конечное число действий получить точное решение системы уравнений, если
входная информация (правая часть уравнения f и элементы aij матрицы A) задана точно, и
вычисления ведутся без округления. Простейший пример прямого метода – метод прогонки.
Конечно, прямые методы также дают решение с определенной точностью, которая зависит от
погрешностей округления, т.е. от машины, и от характера вычислительной устойчивости, что
зависит от самого метода.
        Итерационный метод позволяет найти приближенное решение системы путем построения
последовательности приближений (итераций), начиная с некоторого начального приближения.
Само приближенное решение является результатом вычислений, полученным после конечного
числа итераций.
        Выбор того или иного численного метода зависит от многих обстоятельств – от
имеющихся программ, от вида матрицы, от типа расчета и др. Поясним слова «тип расчета».
Возможны разные постановки задачи:
1) найти решение одной конкретной задачи (1);
2) найти решение нескольких вариантов задачи (1) с одной и той же матрицей A и разными
     правыми частями f. Может оказаться, что неоптимальный для одной задачи (1) метод является
     весьма эффективным для многовариантного расчета.
        При многовариантном расчете можно уменьшить среднее число операций для одного
варианта, если хранить некоторые величины, а не вычислять их заново для каждого варианта. Это,
конечно, зависит от машины, от объема ее оперативной памяти.
        Из сказанного ясно, что выбор алгоритма должен зависеть от типа расчета, от объема
оперативной памяти машины и, конечно, от порядка системы. Качество алгоритма определяется
тем машинным временем, которое требуется для нахождения решения системы (1). Естественно
выбирать тот метод, для которого время решения минимально по сравнению с другими методами.
Однако время расчета зависит от многих факторов: от числа арифметических и логических
действий, которые нужно затратить для получения решения с заданной точностью, от
быстродействия и объема оперативной памяти машины, от качества программы. При
теоретических оценках качества алгоритмов их сравнение приводится по числу Q(ε)
арифметических действий, достаточных для нахождения решения задачи с заданной точностью
ε>0.


                                           3.5.2. Прямые методы

                                           3.5.2.1. Метод Гаусса

       Имеется несколько вычислительных вариантов метода Гаусса, основанного на идее
последовательного исключения. Процесс решения системы линейных алгебраических уравнений
Ax=f, или
                               N

                              ∑a
                               j =1
                                      ij   x j = f j , i=1, 2,…, N,   (1)

по методу Гаусса состоит из двух этапов.
         Первый этап (прямой ход). Система (1) приводится к треугольному виду
                                          B+x=ϕ,          (2)
         где x=(x1,…, xN) – неизвестный, ϕ=(ϕ1,…, ϕN) – известный вектор, B+ – верхняя треугольная
матрица.
         Второй этап (обратный ход). Неизвестные xN, xN-1,…, x1 определяются по формулам (2)
п.3.5.1.
         Перейдем к подробному изложению метода. Первый шаг метода Гаусса состоит в
исключении из всех уравнений, кроме первого, неизвестного x1. Предположим, что a11 ≠ 0,
разделим первое уравнение (1) (i=1) на a11 и запишем систему (1) в виде
                   x1+b12x2+…+b1NxN=ϕ1, b1j=a1j/a11, j=2, 3,…, N, ϕ1=f1/a11,   (3)