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

  Докажем, что метод Зейделя сходится для любой симметричной и положительно определенной матрицы А. 

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

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

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

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

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

  2В>,>0

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

  В силу теоремы  достаточно доказать, что для любой такой матрицы А выполнено условие

  2 (D + L) > А.

  Для доказательства заметим, что для любого вектора X

    (2 (D + L) X, X) = (DX, X) + (DX, X) + (LX, X) + (LX, X) = (DX, X) +

    (DX, X) + (LX, X) + (X,  UX) = (DX, X) + (AX, X).

  Таким образом, для доказательства неравенства достаточно убедиться в положительной определенности матрицы D, но она сразу вытекает из того, что у положительно определенной и симметричной матрицы А все элементы, лежащие на главной диагонали, являются положительными. Сходимость метода Зейделя доказана. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  Метод верхней релаксации

  Этот  метод получается из общего неявного метода простой итерации в том  частном случае, когда , В = D + L, а параметр выбран так, чтобы являлось наименьшим наибольшее по модулю собственное значение матрицы Е-(D + L)^-1 А, осуществляющей переход от к-й итерации к (к + 1)-й.

  Докажем, что если матрица А является симметричной и положительно определенной, то для сходимости метода верхней релаксации достаточно, чтобы было выполнено условие 0 < < 2. 

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

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

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

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

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

  2В>,>0

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

  В силу теоремы для сходимости достаточно выполнение условий ,

  2(D + L) > А.

  Второе  из этих условий для любого вектора  X приводит к неравенству

  (2 (D + L) X, X) >( АХ, X)

  Последнее неравенство эквивалентно каждому  из неравенств в следующей цепочке:

  (2DХ,  X) + ( LX, X) + ( LX, X) > ( АХ, X),

    (2 - ) (DX, X) + ( DX, X) + ( LX, X) + (X, UX) > ( AХ, X),

    (2 - ) (DX, Х) > 0.

  Из  последнего неравенства и из положительной  определенности D заключаем, что

    (2 (D + L) X,X) >( АХ, X)справедливо при 2 - > 0, т. е. при < 2. Итак, доказано, что условия 0 < < 2 обеспечивают сходимость метода верхней релаксации. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  Метод  П.Л. Чебышева

  Этот  метод получается из общего неявного метода простой итерации в том  случае, когда значения итерационного параметра зависят от номера к итерации. В таком случае последовательность итераций будет определяться не соотношением

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

  а более общим соотношением

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

  При этом, как и выше, В — некоторая легко обратимая квадратная матрица порядка п. При таком выборе итерационной последовательности для. погрешности Z_к = X_к — X итерационной схемы получится соотношение

  В ((Z_к+1 - Z_к ) /(_к+1)) + АZ_к =0

  Предположим, что обе матрицы А и В  симметричны и положительно определены. Тогда найдутся положительно определённые постоянные ₁ и ₂ такие, что ₁В < А < ₂В. Пусть постоянные нам заданы равны соответственно наименьшему и наибольшему собственным значениям задачи АХ=ВХ. Оценим энергетическую норму погрешности ||Z_к||_в.

  Для симметричной и положительно определённой матрицы В существует симметричная и положительно определённая матрица В^1/2 такая, что В^1/2 * В^1/2 =В.

  Для оценки нормы погрешности Z_к сделаем замену, положив Z_к = В^{- ½}*V_к. При такой замене соотношение для погрешности Z_к переходит в следующее соотношение для V_к

  V_к+1=(Е-_к+1С)* V_к , к=0,1,2,…  ,

    Где через С обозначена матрица  вида С= В^{- 1/2} * АВ ^-1/2. Квадрат обычной нормы вектора V_к равен квадрату энергетической нормы вектора Z_к.

  ||V_к||²=( V_к , V_к)= (В^1/2Z , В^1/2Z)=(B Z_к ,B Z_к)=|| Z_к||²_B

  Для оценки энергетической нормы Z_к достаточно оценить обычную норму V_к

  Оценим  норму ||V_к||.  Последовательно записывая соотношение V_к+1=(Е-_к+1С)* V_к  для номеров к=0,1,2,… ,придём к следующему равенству

  V_к =

  из  которого сразу же вытекает, что

  ||V_к|| ||_||*V₀.

  Но  тогда из равенства ||V_к||=|| Z_к||_B вытекает, что || Z_к||_B q^к|| Z₀||_B , q_к=||_||. Следовательно, итерационный процесс сходится при условии, что последовательность {q_к} стремится к нулю, причём тем быстрее, чем меньше величина q_к . Поскольку каждое значение q_к  является функцией параметра ₁,₂,…._к возникает задача построения оптимального набора итерационных параметров из условия минимума q_к  для фиксированного к.

  Предположим, что все собственные значения _s матрицы С лежат на отрезке [₁ , ₂], то расширяя область по которой берётся максимум, получим, что 

  Полученная  задача имеет более простое решение. При решение такой задачи не используется информация о конкретном расположении собственных значений _s  на отрезке [₁ , ₂], а учитываются лишь границы этого отрезка. Такой подход позволяет построить набор оптимальных параметров для матрицы произвольной структуры.

  Положим Р(t) = , полином Р(t) удовлетворяет условию нормировки Р(0) = 1. После замены переменной получим, что t = , где =(₂ - ₁) / (₂ + ₁), =2/(₂ + ₁). Отобразим отрезок в отрезок , причём точка t = 0 переходит в .

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

  Таким полином является полином Чебышева ^-1 , 
 

  Так как  , то

  ,

  причём  = q_к =, где .

  Для вычисления оптимального набора параметров будем исходить из равенства

  = q_к.

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

  Этот  итерационный процесс с указанным  оптимальным набором параметров называется чебышевским.

  Теорема: если матрицы А и В симметричны и положительно определены и если ₁В < А < ₂В, то чебышевский процесс сходится, и для погрешности Z_к после выполнения к итераций справедлива оценка

  || Z_к||_B q^к|| Z₀||_B ,

    где q_к = при .

  Если  в качестве окончания процесса взять  для заранее заданной -точности требование