в) | α А | = | α | | А |;

(α — число).

     Под нормой матрицы А = [а_ij ] понимается действительное число || A ||, удовлетворяющее условиям:

а) ||A|| ≥ 0, причем ||A]| =0 тогда и только тогда, когда A = 0;

б) || α А || = | α | ||А ||( α — число) и, в частности, || А || = || А ||;

в) || А + В || ≤ || А || + || В ||;

г) || А В || ≤ || А || || В ||;

(А и  В — матрицы, для которых соответствующие операции имеют смысл).

     В дальнейшем для матрицы А = [а_ij ] произвольного типа мы будем рассматривать главным образом три легко вычисляемые нормы;

1) || А || _m  = | а_ij|        (m-норма);

2)   || А || _l = | а_ij|          (l-норма);

3) || А || _k =               (k -норма).

                                  

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

     Одним из самых распространенных методов  решения систем линейных уравнений  является метод Гаусса. Этот метод (который  также называют методом последовательного исключения неизвестных) известен в различных вариантах уже более 200 лет.

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

      1.4.1 Схема единственного деления

     Рассмотрим  сначала простейший вариант метода Гаусса, называемый схемой единственного  деления.

     Прямой  ход состоит из n - 1 шагов исключения.

     1-й  шаг. Целью этого шага является исключение неизвестного x₁ из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a₁₁ ¹ 0. Будем называть его главным элементом 1-го шага.

      Найдем  величины

      q_i1 = a_i1/a₁₁   (i = 2, 3, …, n),

называемые  множителями 1-го шага. Вычтем последовательно  из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q₂₁, q₃₁, …, q_n1. Это позволит обратить в нуль коэффициенты при x₁ во всех уравнениях, кроме первого. В результате получим эквивалентную систему

      a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁ ,

      a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,

      a₃₂⁽¹⁾x₂ + a₃₃⁽¹⁾x₃ + … + a_3n⁽¹⁾x_n = b₃⁽¹⁾ ,

      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

      a_n2⁽¹⁾x₂ + a_n3⁽¹⁾x₃ + … + a_nn⁽¹⁾x_n = b_n⁽¹⁾ .

в которой  a_ij⁽¹⁾ и b_ij⁽¹⁾ вычисляются по формулам

      a_ij⁽¹⁾ = a_ij − q_i1a_1j    ,    b_i⁽¹⁾ = b_i − q_i1b₁.

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

q_i2 = a_i2⁽¹⁾ / a₂₂⁽¹⁾   (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q₃₂, q₄₂, …, q_m2. В результате получим систему

      a₁₁x₁ + a₁₂x₂ +  a₁₃x₃ + … +  a_1nx_n =  b₁ ,

            a₂₂⁽¹⁾x₂ +  a₂₃⁽¹⁾x₃ + … +  a_2n⁽¹⁾ =  b₂⁽¹⁾ ,

                  a₃₃⁽²⁾x₃ + … +  a_3n⁽²⁾x_n =  b₃⁽²⁾ ,

      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

                  a_n3⁽²⁾x₃ + … +  a_nn⁽²⁾x_n =  b_n⁽²⁾ .

Здесь коэффициенты a_ij⁽²⁾ и b_ij⁽²⁾ вычисляются по формулам

      a_ij⁽²⁾ = a_ij⁽¹⁾ – q_i2a_2j⁽¹⁾   ,    b_i⁽²⁾ = b_i⁽¹⁾ – q_i2b₂⁽¹⁾.

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

     k-й шаг. В предположении, что главный (ведущий) элемент k-го шага a_kk^(k–1) отличен от нуля, вычислим множители k-го шага

      q_ik = a_ik^(k–1) / a_kk^(k–1)   (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на q_k+1,k, q_k+2,k, …, q_nk.

      После (n - 1)-го шага исключения получим систему уравнений

      a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁ ,

            a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,

                  a₃₃⁽²⁾x₃ + … + a_3n⁽²⁾x_n = b₃⁽²⁾ ,

      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

                              a_nn^(n–1)x_n = b_n^(n–1) .

матрица A^(n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

     Обратный  ход. Из последнего уравнения системы находим xn. Подставляя найденное значение x_n в предпоследнее уравнение, получим x_n–1. Осуществляя обратную подстановку, далее последовательно находим x_n–1, x_n–2, …, x₁. Вычисления неизвестных здесь проводятся по формулам

      x_n = b_n^(n–1) / a_nn^(n–1),

      x_k = (b_n^(k–1) – a_k,k+1^(k–1)x_k+1 – … – a_kn^(k–1)x_n) / a_kk^(k–1), (k = n – 1, …, 1).

     Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы a_kk^(k–1). Поэтому если один из главных элементов оказывается равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

1.4.2. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора)

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

a_ij^(k) = a_ij^(k–1) − q_ika_kj , b_i^(k) = b_i^(k–1) − q_ikb_k^(k–1) , i = k + 1, …, n.

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

     В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |q_ik| ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент a_ikk при неизвестной x_k в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером i_k меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента a_kk^(k-1). После этой перестановки исключение неизвестного x_k производят, как в схеме единственного деления.

1.4.3. Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора)

     В этой схеме допускается нарушение естественного порядка исключения неизвестных.

     На 1-м шаге среди элементов a_ij определяют максимальный по модулю элемент a_i1j1. Первое уравнение системы и уравнение с номером i₁ меняют местами. Далее стандартным образом производят исключение неизвестного x_i1 из всех уравнений, кроме первого.

     На  k-м шаге метода среди коэффициентов a_ij^(k–1) при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент a_ikjk^(k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное x_jk из уравнений с номерами i = k + 1, …, n.

     На  этапе обратного хода неизвестные  вычисляют в следующем порядке: x_jn, x_jn–1, …, x_j1.

1.5. Метод Гаусса-Зейделя

      1.5.1. Приведение системы к виду, удобному для итераций

     Для того чтобы применить метод Зейделя  к решению системы линейных алгебраических уравнений

      Ax = b

с квадратной невырожденной  матрицей A, необходимо предварительно преобразовать эту систему к виду

      x = Bx + c.

Здесь B – квадратная матрица с элементами b_ij (i, j = 1, 2, …, n), c – вектор-столбец с элементами c_ij (i = 1, 2, …, n).

     В развернутой форме записи система  имеет следующий вид:

      x₁ = b₁₁x₁ + b₁₂x₂ + b₁₃x₃ + … + b_1nx_n + c₁

      x₂ = b₂₁x₁ + b₂₂x₂ + b₂₃x₃ + … + b_2nx_n + c₂

      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

      x_n = b_n1x₁ + b_n2x₂ + b_n3x₃ + … + b_nnx_n + c_n

     Вообще  говоря, операция приведения системы к виду, удобному для итераций, не является простой и требует специальных знаний, а также существенного использования специфики системы.

     Самый простой способ приведения системы  к виду, удобному для итераций, состоит  в следующем. Из первого уравнения  системы выразим неизвестное  x₁:

      x₁ = a₁₁^–1 (b₁ – a₁₂x₂ – a₁₃x₃ – … – a_1nx_n),

из второго  уравнения – неизвестное x₂:

      x₂ = a₂₁^–1 (b₂ – a₂₂x₂ – a₂₃x₃ – … – a_2nx_n),

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

      x₁ =  b₁₂x₂ + b₁₃x₃ + … + b_1,n–1x_n–1 + b_1nx_n+ c₁ ,

      x₂ = b₂₁x₁ +  b₂₃x₃ + … + b_2,n–1x_n–1 + b_2nx_n+ c₂ ,