Простое рациональное приближение

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

Основное применение SRA заключается в нахождении нулей вековых функций . Алгоритм «разделяй и властвуй» для поиска собственных значений и собственных векторов для различных видов матриц хорошо известен в численном анализе . В строгом смысле SRA подразумевает специальную интерполяцию с использованием простых рациональных функций как часть алгоритма «разделяй и властвуй». Поскольку такие вековые функции состоят из ряда рациональных функций с простыми полюсами, SRA является лучшим кандидатом для интерполяции нулей вековой функции. Более того, согласно предыдущим исследованиям, простой нуль, расположенный между двумя соседними полюсами, можно значительно хорошо интерполировать, используя рациональную функцию с двумя доминантными полюсами в качестве аппроксимирующей функции.

Одноточечный итерационный метод третьего порядка: формула Галлея

Происхождение интерполяции с рациональными функциями можно найти в предыдущей работе Эдмонда Галлея . Формула Галлея известна как одноточечный итерационный метод третьего порядка для решения $\,f(x)=0$ путем аппроксимации рациональной функции, определяемой формулой

$h(z)={\frac {a}{z+b}}+c.$

Мы можем определить a, b и c так, что

$h^{(i)}(x)=f^{(i)}(x),\qquad i=0,1,2.$

Затем решение $\,h(z)=0$ дает итерацию

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\left({\frac {1}{1-{\frac {f(x_{n})f''(x_{n})}{2(f'(x_{n}))^{2}}}}}\right).$

Это называется формулой Галлея.Эта геометрическая интерпретация $h(z)$ был получен Гандером (1978), где эквивалентная итерация также была получена путем применения метода Ньютона к

$g(x)={\frac {f(x)}{\sqrt {f'(x)}}}=0.$

Мы называем эту алгебраическую интерпретацию $g(x)$ формулы Галлея.

Одноточечный итерационный метод второго порядка: простая рациональная аппроксимация

Аналогичным образом мы можем вывести вариант формулы Галлея, основанный на одноточечном итерационном методе второго порядка для решения $\,f(x)=\alpha (\neq 0)$ используя простое рациональное приближение с помощью

$h(z)={\frac {a}{z+b}}.$

Затем нам нужно оценить

$h^{(i)}(x)=f^{(i)}(x),\qquad i=0,1.$

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

$x_{n+1}=x_{n}-{\frac {f(x_{n})-\alpha }{f'(x_{n})}}\left({\frac {f(x_{n})}{\alpha }}\right).$

Алгебраическая интерпретация этой итерации получается путем решения

$g(x)=1-{\frac {\alpha }{f(x)}}=0.$

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

Заметим, что даже метод третьего порядка является разновидностью метода Ньютона. Мы видим, что шаги Ньютона умножаются на некоторые факторы. Эти факторы называются коэффициентами сходимости вариаций, которые полезны для анализа скорости сходимости. См. Гандер (1978).

Ссылки

• Деммель, Джеймс В. (1997), Прикладная числовая линейная алгебра , Филадельфия, Пенсильвания: Общество промышленной и прикладной математики , ISBN  0-89871-389-7 , МР   1463942 .
• Элхай, С.; Голуб, GH ; Рам, Ю.М. (2003), «Спектр модифицированного линейного карандаша», Computers & Mathematics with Applications , 46 (8–9): 1413–1426, doi : 10.1016/S0898-1221(03)90229-X , MR   2020255 .
• Гу, Мин; Эйзенстат, Стэнли К. (1995), «Алгоритм «разделяй и властвуй» для симметричной трехдиагональной задачи собственных чисел» (PDF) , SIAM Journal on Matrix Analysis and Applications , 16 (1): 172–191, doi : 10.1137/S0895479892241287 , МР   1311425 .
• Гандер, Уолтер (1978), О линейной задаче наименьших квадратов с квадратичным ограничением , Стэнфордский университет , Школа гуманитарных наук, факультет компьютерных наук .