Эти формулы как раз и задают собственно итерационный процесс.

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

      Это условие можно сформулировать и  более точно:

      Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма  отношений коэффициентов системы  к диагональным элементам, взятым из той же строки, была строго меньше единицы:

      

3. Следует так  же сказать, что итерационный процесс  может проводиться как в виде итерации Якоби, так и в виде итерации Гаусса-Зейделя. В последнем случае сходимость итерационного процесса может существенно улучшиться.

    Глава 2. Применение численных методов для решения систем линейных алгебраических уравнений в теории и на практике

      §1 ЧИСЛЕННЫЕ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

 
 

     Существуют  два типа методов — прямые и итерационные. Мы рассматриваем прежде всего метод исключения Гаусса для систем общего вида и варианты — метод прогонки и методы матричной прогонки для систем специального вида (с трех-диагональной или блочно-трех диагональной матрицами). Это — прямые методы. Их эффективность зависит от порядка системы n структуры матрицы.

     При изучении итерационных методов мы трактуем систему уравнений как операторное уравнение первого рода Au = f и излагаем общую теорию итерационных методов для операторных уравнений при минимальных предположениях относительно оператора А. Общая теория позволяет доказать сходимость итераций для метода Зейделя и метода верхней релаксации при минимальных ограничениях на оператор А. Рассмотрены два класса методов: 1) для случая, когда известны границы γ_i > О и γ₂ >= γ₁ спектра оператора А в некотором энергетическом пространстве H_D; 2) для случая, когда границы γ₁ и γ₂ неизвестны. Весьма эффективным является попеременно-треугольный метод.

     Основная  задача линейной алгебры — решение системы уравнений

Au = f, (1)

где u=(u⁽¹⁾, ..., u^(N)) — искомый вектор, f={f⁽¹⁾, f⁽²⁾,... ..., f⁽ⁿ⁾)—известный вектор размерности N, A=(a_ij) (i, j = 1, 2, ..., N)— квадратная матрица размера NXN с элементами a_ij.

      Будем предполагать, что матрица А невырождена, так что уравнение Аи = 0 имеет только тривиальное решение, и система (1) имеет единственное решение

      В курсе линейной алгебры решение  системы (1) обычно выражают по формулам Крамера в виде отношений определителей. Для численного решения системы (1) эти формулы непригодны, так как они требуют вычисления N +1 определителей, что требует большого числа действий (порядка N! арифметических операций). Даже при выборе наилучшего метода вычисление одного определителя требует примерно такого же времени, что и решение системы линейных уравнений современными численными методами. Кроме того, следует иметь в виду, что вычисления по формулам Крамера часто ведут к большим ошибкам округлений.

      Особенность большинства численных методов  для (1) состоит в отказе от нахождения обратной матрицы. Основное требование к методу решения — минимум числа арифметических действий, достаточных для отыскания приближенного решения с заданной точностью е>0 (экономичность численного метода).

     Выбор того или иного численного метода зависит от многих обстоятельств — от имеющихся программ, от вида матрицы А, от типа расчета и др. Поясним слова «тип расчета». Возможны разные постановки задачи:

1. найти решение одной конкретной задачи (1);
2. найти решение нескольких вариантов задачи (1) с одной и той же матрицей А и разными правыми частями. Может оказаться, что неоптимальный для одной задачи метод является весьма эффективным для многовариантного расчета.

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

     При теоретических оценках качества алгоритмов их сравнение проводится по числу q(e) арифметических действий, достаточных для нахождения решения задачи с заданной точностью е > 0 [15].

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

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

  Первый  этап (прямой ход). Система (1) приводится к треугольному виду

х + В*х = φ, (2)

где x=(x₁, ..., x_N-) - неизвестный,  φ= (φ_1,…,φ_N) —известный векторы, В* — верхняя треугольная матрица.

  Второй  этап (обратный ход). Неизвестные х_N, x_N-1, ..., x₁ определяются по формулам (2) .

     Метод квадратного корня. Этот метод пригоден для систем

Au = f (3)

с эрмитовой (в действительном случае — симметричной) матрицей А. Матрица А разлагается в произведение

А -= S*DS, (4)

где S — верхняя треугольная, D — диагональная матрица. Решение уравнения Аu=f сводится к последовательному решению двух систем

S*Dy = f,   Su = y. (5)

  Метод квадратного корня требует порядка  N²/3 арифметических действий, т. е. при больших N он вдвое быстрее метода Гаусса и занимает вдвое меньше ячеек памяти. Это обстоятельство объясняется тем, что метод использует информацию о симметрии матрицы.

   Итерационные  методы

  1. Метод итераций для решения системы линейных алгебраических уравнений.

  Перейдем  к общему описанию метода итераций для системы линейных алгебраических уравнений

Au=f (6)

  Для ее решения выбирается некоторое  начальное приближение у₀ H и последовательно находятся приближенные решения (итерации) уравнения (1). Значение итерации y_h+1 выражается через известные предыдущие итерации y_k, y_k-1,… Если при вычислении y_h+1 используется только одна предыдущая итерация y_h, то итерационный метод называют одношаговым (или двухслойным) методом; если же y_k+1 выражается через две итерации y_k и y_k-1, то метод называется двухшаговым (или трехслойным). Мы будем рассматривать в основном одношаговые методы. Будем считать, что А: H->H — линейный оператор в конечномерном пространстве H со скалярным произведением (•, •).

  Важную  роль играет запись итерационных методов  в единой (канонической) форме. Любой двухслойный итерационный метод можно записать в следующей канонической форме:

   (7) , где А: Н -> Н — оператор исходного уравнения (1), В: Н -> Н — линейный оператор, имеющий обратный В^-1, k — номер итерации, τ₁ τ₂, ..., τ_k+1, ...— итерационные параметры, τ_k+1> 0. Оператор В может, вообще говоря, зависеть от номера k- для Для простоты изложения мы предполагаем всюду, что В не зависит от k.

   Если  В = Е — единичный оператор, то метод (8) называют явным: y_h+1 находится по явной формуле

 

     В общем случае, при В≠ Е, метод (7) называют неявным итерационным методом: для определения y_h+1 надо решить уравнение:

   (9)

     Естественно требовать, чтобы объем вычислений для решения .системы By_k+1 = F_k был меньше, чем объем вычислений для прямого решения системы Au=f

      Точность  итерационного метода (7) характеризуется  величиной погрешности z_h = у_к — и, т. е. разностью между решением уравнения (7) и точным решением и исходной системы линейных алгебраических уравнений. Подстановка y_k = z_k+u в (2) приводит к однородному уравнению для погрешности:

    §2 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

      2.1 Общие сведения

 

     К численным методам линейной алгебры  относятся численные методы решения  систем линейных алгебраических уравнений. Методы решения СЛАУ разбиваются на две группы. К первой группе принадлежат так называемые точные или прямые методы - алгоритм, позволяющий получить решение системы за конечное число арифметических действий. Вторую группу составляют приближенные методы, в частности итерационные методы решения СЛАУ.

      2.2.1 Описание метода

Рассмотрим  СЛАУ вида

Ax = B, где А - матрица. (1) 

A = {a_ij}i, j = 1…n

B = {b_i}x = {x_i} 

Если  эту систему удалось привести к виду x = Cx + D, то можно построить итерационную процедуру 

x_k = Cx_k-1 + D 

x_k → x*, где х* - решение заданной системы.

В конечном варианте система будет имееть вид: 

x₁=c₁₁x₁+c₁₂x₂+c₁₃x₃+…c_1nx_n+d₁

x₂=c₂₁x₁+c₂₂x₂+c₂₃x₃+…c_2nx_n+d₁

x₃=c₃₁x₁+c₃₂x₂+c₃₃x₃+…c_1nx_n+d₃

_{…………………………………………. .}

x_n=c_n1x₁+c_n2x₂+c_n3x₃+…c_nnx_n+d_n 

Условием  сходимости для матрицы С выполняется, если сумма модулей коэффициентов меньше единицы по строкам или по столбцам, т.е. 

, или  . 

Необходимо, чтобы диагональные элементы матрицы  А были ненулевыми.

Для преобразования системы можно выполнить следующие операции: 

x₁₌a₁₁^-1 (c₁-a₁₂x₂ - a₁₃x₃-… - a_1nx_n)

x₂₌a₂₂^-1 (c₂-a₂₁x₂ - a₂₃x₃-… - a_2nx_n)

………………………. .

x_n=a_nn^-1 (c_n-a_n1x₂ - a_n3x₃-… - a_n-1nx_n-1)

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

x₁₌0+ c₁₂x₂+ c₁₃x₃-…+ c_1n-1x_n-1+ c_1nx_n+d₁

x₂₌ c₂₁x₂+0 +c₂₃x₃+…+ c_2n-1x_n-1+ c_2nx_n+d₂

_{………………………………………………………. .}

x_n= c_n1x₁+ c_n2x₂ +c_n3x₃+…+ c_nn-1x_n-1+ 0+d_n 

В ней  на главной диагонали матрицы  С находятся нулевые элементы, остальные элементы выражаются по формулам: 

с_ij=-a_ij/a_ii, d_i=c_i/a_ii (i,j=1,2,3…n, i<>j) 

Итерационный  процесс продолжается до тех пор, пока значения х₁ ^(k), х₂ ^(k), х₃ ^(k) не станут близкими с заданной погрешностью к значениям х₁ ^(k-1), х₂ ^(k-1), х₃ ^(k-1).

      2.2.2 Решение СЛАУ методом простых итераций

 

Решить  СЛАУ методом простых итераций с  точностью .