Модифицированная итерация Ричардсона

Модифицированная итерация Ричардсона — итерационный метод решения системы линейных уравнений . Итерация Ричардсона была предложена Льюисом Фраем Ричардсоном в его работе, датированной 1910 годом. Она похожа на метод Якоби и Гаусса–Зейделя .

Мы ищем решение системы линейных уравнений, выраженное в матричных терминах как

${\displaystyle Ax=b.\,}$

Итерация Ричардсона — это

${\displaystyle x^{(k+1)}=x^{(k)}+\omega \left(b-Ax^{(k)}\right),}$

где — скалярный параметр, который необходимо выбрать таким образом, чтобы последовательность сходилась.${\displaystyle \омега}$${\displaystyle x^{(k)}}$

Легко видеть, что метод имеет правильные неподвижные точки , поскольку если он сходится, то и должен приближать решение .${\displaystyle x^{(k+1)}\approx x^{(k)}}$${\displaystyle x^{(k)}}$${\displaystyle Ах=b}$

Вычитая точное решение и вводя обозначение для погрешности , получаем равенство для погрешностей${\displaystyle x}$${\displaystyle e^{(k)}=x^{(k)}-x}$

${\displaystyle e^{(k+1)}=e^{(k)}-\omega Ae^{(k)}=(I-\omega A)e^{(k)}.}$

Таким образом,

${\displaystyle \|e^{(k+1)}\|=\|(I-\omega A)e^{(k)}\|\leq \|I-\omega A\|\|e^{(k)}\|,}$

для любой векторной нормы и соответствующей индуцированной матричной нормы. Таким образом, если , метод сходится.${\displaystyle \|I-\omega A\|<1}$

Предположим, что симметрично положительно определено и что являются собственными значениями . Ошибка сходится к , если для всех собственных значений . Если, например, все собственные значения положительны, это может быть гарантировано, если выбрано таким образом, что . Оптимальным выбором, минимизирующим все , является , что дает простейшую итерацию Чебышева . Этот оптимальный выбор дает спектральный радиус ${\displaystyle А}$${\displaystyle (\lambda _{j})_{j}}$${\displaystyle А}$${\displaystyle 0}$${\displaystyle |1-\omega \lambda _{j}|<1}$${\displaystyle \lambda _{j}}$${\displaystyle \омега}$${\displaystyle 0<\omega <\omega _{\text{max}}\,,\ \omega _{\text{max}}:=2/\lambda _{\text{max}}(A)}$${\displaystyle |1-\omega \lambda _{j}|}$${\displaystyle \omega _{\text{opt}}:=2/(\lambda _{\text{min}}(A)+\lambda _{\text{max}}(A))}$

${\displaystyle \min _{\omega \in (0,\omega _{\text{max}})}\rho (I-\omega A)=\rho (I-\omega _{\text{opt}}A)=1-{\frac {2}{\kappa (A)+1}}\,,}$

где - номер состояния .${\displaystyle \kappa (A)}$

Если имеются как положительные, так и отрицательные собственные значения, метод будет расходиться для любого, если начальная ошибка имеет ненулевые компоненты в соответствующих собственных векторах .${\displaystyle \omega }$${\displaystyle e^{(0)}}$

Рассмотрим минимизацию функции . Поскольку это выпуклая функция , достаточным условием оптимальности является равенство нулю градиента ( ), что приводит к уравнению${\displaystyle F(x)={\frac {1}{2}}\|{\tilde {A}}x-{\tilde {b}}\|_{2}^{2}}$${\displaystyle \nabla F(x)=0}$

${\displaystyle {\tilde {A}}^{T}{\tilde {A}}x={\tilde {A}}^{T}{\tilde {b}}.}$

Определим и . Из-за формы A это положительно полуопределенная матрица , поэтому она не имеет отрицательных собственных значений.${\displaystyle A={\tilde {A}}^{T}{\tilde {A}}}$${\displaystyle b={\tilde {A}}^{T}{\tilde {b}}}$

Шаг градиентного спуска - это

${\displaystyle x^{(k+1)}=x^{(k)}-t\nabla F(x^{(k)})=x^{(k)}-t(Ax^{(k)}-b)}$

что эквивалентно итерации Ричардсона путем создания .${\displaystyle t=\omega }$

• Экстраполяция Ричардсона

• Ричардсон, Л. Ф. (1910). «Приближенное арифметическое решение с помощью конечных разностей физических задач, включающих дифференциальные уравнения, с приложением к напряжениям в каменной плотине». Philosophical Transactions of the Royal Society A. 210 ( 459–470 ) : 307–357 . doi :10.1098/rsta.1911.0009. JSTOR  90994.
• Лебедев, Вячеслав Иванович (2001) [1994], "Метод итераций Чебышева", в Michiel Hazewinkel (ред.), Encyclopedia of Mathematics , EMS Press , ISBN 1-4020-0609-8, получено 2010-05-25