Численные методы решения систем линейных уравнений

  Система содержит теперь t уравнений, причём ts, так как некоторые уравнения оказались, возможно, отброшенными.

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

1. либо мы придём к системе, в которой одно из уравнений имеет отличный от нуля свободный член, а все коэффициенты левой части равны нулю. В этом случае исходная система несовместна.
2. либо мы получим совместную систему:

 
 

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

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

  Метод простой итерации (метод Якоби)

  Рассмотрим  систему линейных уравнений с  вещественными коэффициентами, записанную в матричном виде: АХ = F.

  Предполагая однозначную разрешимость системы, заменим матричное уравнение 

  эквивалентным ему матричным уравнением  , в котором через обозначено вещественное число, обычно называемое стационарным параметром. С помощью последнего уравнения составим итерационную последовательность векторов , определив её рекуррентным соотношением 

  при произвольном выборе «нулевого» приближения.

  Метод  итерации  заключается в замене точного решения  системы-ой итераций с достаточно большим номером . Оценим погрешность   метода простой итерации.

  Отсюда  вытекает следующее матричное уравнение  для погрешности 

  ,

  где - единичная матрица порядка n. 

  Введем  в рассмотрение норму вектора  в пространстве Е^п и операторную норму квадратной матрицы порядка n. Как обычно, назовем нормой вектора X число ||X||, равное корню квадратному из суммы квадратов координат этого вектора. Назовем операторной нормой произвольной матрицы А число , равное либо точной верхней грани отношения на множестве всех ненулевых векторов X, либо (что то же самое) точной верхней грани норм на множестве всех векторов X, имеющих норму, равную единице.

  Итак, по определению 

  Напомним, что для любой симметричной матрицы  A операторная норма этой матрицы равна наибольшему по модулю собственному значению этой матрицы. 
 

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

  Из  матричного уравнения для погрешности  и из неравенства 
мы получим, что для любого номера k 
 

  Теорема: Для того чтобы итерационная последовательность при любом выборе нулевого приближения Х₀ и при данном значении параметра сходилась к точному решению X системы , достаточно, чтобы было выполнено условие 

  При этом последовательность сходится со скоростью геометрической  прогрессии со знаменателем 

  В случае, если матрица  А является симметричной, это условие является и необходимым условием сходимости итерационной последовательности при любом выборе нулевого приближения Х₀.

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

  Пусть задана -точность, с которой нам требуется получить точное решение системы. Требуется найти итерацию X_к с таким номером к, для которого  

    Из условия  вытекает, что , и, стало быть выполняется при , т. е. при .

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

  Считая  матрицу А симметричной и положительно определенной, мы приходим к следующей задаче оптимизации: найти минимум функции 
 

  Минимум функции  достигается для значения , где ₁ и ₂ — соответственно минимальное и максимальное собственные значения матрицы А, причем минимальное значение функции равно

  . 

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

  Общий неявный метод простой итерации

  Рассмотрим  систему линейных уравнений с вещественными коэффициентами, записанную в матричной виде: АХ = F.

  Заменим итерационную последовательность более  общей итерационной последовательностью, определяемой соотношением:

  В ((Х_к+1 - Х_к ) /()) + АХ_к =F.

  в котором В представляет собой некоторую «легко обратимую» квадратную матрицу n-го порядка, а - стационарный параметр. Такой метод составления итерационной последовательности и называется неявным методом простой итерации. Явный метод простой итерации получается из неявного метода в частном случае В =  Е, где Е —единичная матрица порядка п.

  Матрица А называется положительно определенной, если (АХ, X) > 0 для любого ненулевого вектора X. Необходимым и достаточным условием положительной определенности симметричной матрицы А (или, что то же самое, самосопряженного линейного оператора А) является положительность всех собственных значений этой матрицы (этого оператора).

  Если  матрица А является положительно определенной, то А > 0, В > А (или А <<В) в случае, если В — А > 0 (т. е. если матрица В—А является положительно определенной).

  Теорема: Пусть матрица А является симметричной и выполнены условия А > 0,

  В > 0 (симметричность матрицы В, вообще говоря, предполагается) .

  Тогда для того чтобы  итерационная последовательность, определяемая соотношением

  В ((Х_к+1 - Х_к ) /()) + АХ_к =F

  при любом выборе нулевого приближения Х₀ сходилась к точному решению X системы АХ = F достаточно, чтобы были выполнены условия

  2В>,>0

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

  Для оценки скорости сходимости неявного метода простой итерации введём энергетическую норму вектора Х, положив её равной _в = и обозначим _в.

  Энергетическая  норма вектора Х и его обычная  норма эквивалентны. Эта эквивалентность  обычной и энергетической норм можно  утверждать, что последовательность ||Х_к|| сходится к нулю тогда и только тогда, когда сходится к нулю последовательность ||Х_к||_в.

  Теорема: Пусть матрицы А и В симметричны и положительно определены, Z_к обозначает погрешность общего неявного метода простой итерации. Тогда, для того чтобы при было справедливо неравенство  ||Z_к||_в < ^к ||Z₀||_в  достаточно,  чтобы  было выполнено условие 

    В В 

  Основной  задачей является выбор такого параметра , при котором скорость сходимости является максимальной. Из неравенства ||Z_к||_в < ^к ||Z₀||_в  вытекает, что эта задача сводится к нахождения такого значения , при котором достигается минимальное значение функции .

  Так как обе матрицы А и В симметричны и положительно определены, то существуют положительные постоянные ₁ и ₂ такие, что справедливы неравенства ₁В < А < ₂В. Будем считать, что постоянные ₁ и ₂ в этих неравенствах нам заданы. Сопоставляя написанные неравенства с условием В В, мы получим, что минимальное значение   достигается при условии ₁, ₂ откуда получаем, оптимальное значение ₁+₂) и минимальное значение , равное

  (₂ - ₁) / (₂ + ₁). 
 
 
 
 
 

  Метод Зейделя

  Представим  симметричную матрицу А в виде суммы трёх матриц А=D+L+U, где

    D-диагональная матрица, а L и U-строго левая и строго правая  матрицы удовлетворяющие условию L`=U.

  Метод Зейделя получается из общего неявного метода простой итерации в том  частном случае, когда стационарный параметр равен единице, а матрица В равна сумме D + L. Таким образом, последовательные итерации в методе Зейделя определяются соотношением

  (D + L) (Х_к+1 - Хк) + AX_к = F.