Применение интерполяции для решения уравнений

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Содержание

1 Постановка задачи
2 Сравнение методов
3 Анализ методов
4 Вывод
5 Литература
6 Смотри также

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

Постановка задачи

Пусть на отрезке [a,b] задана функция f(x), и необходимо решить уравнение f(x) = 0 на этом отрезке. Известно много различных способов нахождения корней уравнения, но мы поступим следующим образом: будем приближать исходную функцию f(x) другой функцией g(x) и искать корни именно интерполированной (в англоязычной аббревиатуре - Interpolation) функции g(x).

Рассмотрим следующие методы интерполяции:

Сравнение методов

Сравним методы интерполяции функций и выясним, какой из них лучше использовать для нахождения корней уравнения f(x) = 0 в конкретном случае. В конечном итоге предстоит определить, насколько точно корни уравнения g(x) = 0 приближают корни уравнения f(x) = 0.

Интерполяция каноническим полиномом

Рассмотрим в качестве функции f(x) = sin(x) на [1,8], а в качестве интерполирующей функции g(x) – полином, имеющий следующий вид: $g(x) = P_n(x) = c_0 + c_1x + c_2x^2 + \ldots + c_nx^n$

В качестве узлов интерполяции выберем точки на отрезке [1,8] по алгоритму Чебышева. При выборе 8 узлов получается наименьшая ошибка интерполяции (она равна 0.0124).

График синуса (показан синим цветом) и интерполирующей функции (показан красным цветом) в этом случае выглядит так:

Корни полинома g(x) = 0 будем искать, например, методом Гаусса. Ошибка при нахождении поиске складывается из ошибки интерполяции и ошибки решения уравнения.

Погрешность интерполяции: $|R_n(x)| = \frac{M_{n+1}}{(n+1)!}\omega_n(x)$
Сложность метода Гаусса: O(2n/3).

Интерполяция полиномами Лагранжа

Рассмотрим в качестве f(x) ту же функцию sin(x), но на этот раз на отрезке [-3,3], а в качестве интерполирующей функции g(x) рассмотрим полином: $P_n(x) = \sum_{i=0}^n y_i Q_{n,i}(x),$ где $Q_{n,i}(x)$ - полиномы степени n вида $Q_{n,i}(x) = \prod_{j=0, \\ j \neq i}^n \frac{x-x_j}{x_i - x_j}$

В качестве узлов интерполяции снова по алгоритму Чебышева выберем точки на отрезке [-3, 3].

График синуса (показан красным цветом) и интерполирующей функции (показан зелёным цветом) в этом случае выглядит так:

Уравнение Лагранжа g(x) = 0 решается проще, чем f(x) = 0. При этом ошибка приближения: 0.0944, погрешность интерполяции: $|R_n(x)| = \frac{f^{n+1}(\xi)}{(n+1)!}\omega_{n+1}(x).$

Ошибка нахождения корней снова складывается из ошибки интерполяции и ошибки решения уравнения Лагранжа.

Интерполяция степенными рядами

В качестве f(x) снова рассматриваем sin(x) на [-1, 1], g(x) в данном случае имеет следующий вид: $g(x) = \sum_{n=0}^\infty f^{(n)}(x_0)\frac{(x-x_0)^n}{n!}$

Графики показаны на следующем рисунке:

Ошибка приближения в этом случае больше, поэтому данный метод интерполяции менее предпочтителен для поиска корней, погрешность интерполяции: $f(x) = f^{(n+1)}(\xi)\frac{(x-x_0)^{n+1}}{(n+1)!}$

Интерполяция кубическими сплайнами

f(x) = sin(x) на [-1, 1]. g(x) - сплайн-интерполяция синуса, функцию f(x) пытаемся представить в виде некоторых элементарных функций: $f(x)=\sum_{k=0}^N {c_k\Phi_k(x)},$ где $\{\Phi_k(x)\}$ — фиксированный линейно независимые функции, $c_0, c_1, \cdots, c_n$ — не определённые пока коэффициенты.

При выборе шага h = 0.25 интерполяция выглядит так:

Ошибка интерполяции оценивается как $\parallel g-f\parallel \le \frac{5}{384}h^4\parallel \frac{d^4f}{df^4}\parallel$

Тригонометрическая интерполяция

На этот раз разложим функцию f(x) (считаем её непрерывно-дифференцируемой) в ряд Фурье: $f(x)=\sum_{k=-\infty}^{\infty} \alpha_k exp{2\pi i k x}$ , где $\alpha_k=\int \limits_{0}^{1} f(x) exp {-2 \pi i k x} dx.$

Для её приближения будем использовать тригонометрический полином следующего вида: $\begin{matrix}g(x) = F_n(x)=a_0 & + & a_1 \cos x + a_2 \cos 2x+\dots + a_n \cos nx + \\ \ &+&b_1 \sin x + b_2 \sin 2x+\dots + b_n \sin nx . \end{matrix}$

Тогда приближение функции f(x) функцией g(x) будет выглядеть примерно следующим образом:

Поиск корней тригонометрической функции осуществляется итерационным методом. Анализ данного метода будет дан ниже.

Анализ методов

При решении уравнения f(x) = 0 вместо поиска корней исходной функции f(x) мы переходили к интерполирующей функции g(x) и искали её корни. Но какой же метод аппроксимации лучше для поиска корней?

Однозначного ответа на данный вопрос быть не может - это зависит от функции f(x). С одной стороны, надо использовать тот метод, который лучше приближает исходную функцию f(x). С другой стороны, мы должны достаточно точно отыскать корни g(x).

Например, если сравнивать интерполяцию каноническим полиномом и полиномами Лагранжа, то лучше использовать второй метод, ибо он наиболее точно и с меньшими затратами приближает требуемую функцию, а сложность решения уравнения g(x) = 0 у них одинакова.

А интерполяцию кубическими сплайнами рационально применять, если f(x) - периодическая или тригонометрическая функция. В случае приближения сплайнами, например, кусочно-линейной функции возникает следующий эффект:

Понятно, что ни о какой точности решения уравнения g(x) = 0 говорить не приходится.

Вывод

Были рассмотрены следующие методы интерполяции исходной функции для решения уравнения f(x) = 0:

Интерполяция каноническим полиномом
Интерполяция полиномами Лагранжа
Интерполяция степенными рядами
Интерполяция кубическими сплайнами
Тригонометрическая интерполяция

Установлено, что точность решения интерполяционного уравнения зависит от вида функции f(x). В результате чего в качестве рекомендации предлагается следующее:

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

Литература

Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. Изд-во "Лаборатория базовых знаний". Москва. 2003.
И.С. Березин, Н.П. Жидков. Методы вычислений. Изд. ФизМатЛит. Москва. 1962.
А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
А.А.Самарский. Введение в численные методы М.: Наука, 1982.
Дж. Форсайт, М.Мальком, К. Моулер. Машинные методы математических вычислений. Изд-во "Мир". Москва. 1980.

Смотри также

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D0%B8_%D0%B4%D0%BB%D1%8F_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D1%8F_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B9»

Категория: Учебные задачи

@@ Строка 1: / Строка 1: @@
 {{TOCright}}
+В настоящем исследовании будут рассмотрены методы решения уравнения ''f(x)'' = 0 с помощью применения интерполяции. Мы выясним, есть ли преимущества при замене исходной функции на интерполяционную функцию, и какова точность нахождения корня при переходе к решению интерполяционного уравнения.
 == Постановка задачи ==
@@ Строка 35: / Строка 37: @@
 Рассмотрим в качестве ''f(x)'' ту же функцию  sin(''x''), но на этот раз на отрезке [-3,3], а в качестве интерполирующей функции ''g(x)'' рассмотрим полином:
-<tex>P_n(x) = \sum_{i=0}^n y_i Q_{n,i}(x),</tex> где <tex>Q_{n,i}(x)</tex> - полиномы степени ''n'' вида <tex>\texstyle Q_{n,i}(x) = \prod_{j=0, \\ j \neq i}^n  \frac{x-x_j}{x_i - x_j}</tex>
+<tex>P_n(x) = \sum_{i=0}^n y_i Q_{n,i}(x),</tex> где <tex>Q_{n,i}(x)</tex> - полиномы степени ''n'' вида <tex>Q_{n,i}(x) = \prod_{j=0, \\ j \neq i}^n  \frac{x-x_j}{x_i - x_j}</tex>
 В качестве узлов интерполяции снова по алгоритму Чебышева выберем точки на отрезке [-3, 3].
@@ Строка 63: / Строка 65: @@
 ''f(x)'' = sin(''x'') на [-1, 1]. ''g(x)'' - сплайн-интерполяция синуса, функцию ''f(x)'' пытаемся представить в виде некоторых элементарных функций:
-<tex>f(x)=\sum_{k=0}^N {c_k\Phi_k(x)},</tex> где <tex>\{\Phi_k(x)\}</tex> — фиксированный линейно независимые функции, <tex>c_0, c_1, \cdots, c_n</tex> — не определенные пока коэффициенты.
+<tex>f(x)=\sum_{k=0}^N {c_k\Phi_k(x)},</tex> где <tex>\{\Phi_k(x)\}</tex> — фиксированный линейно независимые функции, <tex>c_0, c_1, \cdots, c_n</tex> — не определённые пока коэффициенты.
-При выборе шага ''h'' = 0.25 интерполяция выглядет так:
+При выборе шага ''h'' = 0.25 интерполяция выглядит так:
 [[Изображение:Interpolation result sin 0,25.png]]
@@ Строка 92: / Строка 94: @@
 Например, если сравнивать интерполяцию каноническим полиномом и полиномами Лагранжа, то лучше использовать второй метод, ибо он наиболее точно и с меньшими затратами приближает требуемую функцию, а сложность решения уравнения ''g(x)'' = 0 у них одинакова.
-А интерполяцию кубичискими сплайнами рационально применять, если ''f(x)'' - периодическая или тригонометрическая функция. В случае приближения сплайнами, например, кусочно-линейной функции возникает следующий эффект:
+А интерполяцию кубическими сплайнами рационально применять, если ''f(x)'' - периодическая или тригонометрическая функция. В случае приближения сплайнами, например, кусочно-линейной функции возникает следующий эффект:
 [[Изображение:Kusochnozadannaya.png]]
@@ Строка 129: / Строка 131: @@
 * [[Тригонометрическая интерполяция]]
 * [[Практикум ММП ВМК, 4й курс, осень 2008]]
+[[Категория:Учебные задачи]]