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

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

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

$Ax=b.\,$

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

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

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

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

Конвергенция

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

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

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

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

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

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

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

где $\kappa (A)$ это номер состояния .

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

Эквивалентность градиентному спуску

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

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

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

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

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

что эквивалентно итерации Ричардсона, делая $t=\omega$.

См. также

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

Ссылки

• Ричардсон, LF (1910). «Приближенное арифметическое решение с помощью конечных разностей физических задач, включающих дифференциальные уравнения, с применением к напряжениям в каменной плотине». Философские труды Королевского общества А. 210 : 307–357. дои : 10.1098/rsta.1911.0009 . JSTOR   90994 .
• Лебедев, Вячеслав Иванович (2001) [1994], «Итерационный метод Чебышева» , в Михиэле Хазевинкеле (редактор), Энциклопедия математики , EMS Press , ISBN  1-4020-0609-8 , получено 25 мая 2010 г.