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

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

Версия от 21:00, 23 ноября 2008; Leo (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Содержание

В настоящем исследовании будут рассмотрены методы решения уравнения 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).

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

Изображение:Report1-fig4-7-2pts.gif

Корни полинома 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].

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

Изображение:2sinlag.gif

Уравнение Лагранжа 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!}

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

Изображение:Different series.png

Ошибка приближения в этом случае больше, поэтому данный метод интерполяции менее предпочтителен для поиска корней, погрешность интерполяции: 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 интерполяция выглядит так:

Изображение:Interpolation result sin 0,25.png

Ошибка интерполяции оценивается как \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) будет выглядеть примерно следующим образом:

Изображение:Slide1.gif

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

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

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

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

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

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

Изображение:Kusochnozadannaya.png

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

Вывод

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

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

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

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

Литература

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

Смотри также

Источник — «http://poligon.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»