Реферат Итерациональные методы решения нелинейных уравнений

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 11.11.2024

ГЛАВА 5. Методы приближения ФУНКЦИЙ.

§5.1. Постановка задачи аппроксимации и интерполяции функций.

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

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

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

Повод для аппроксимации может возникнуть даже тогда, когда аналитическое выражение некоторой функции имеется, однако оно оказывается мало пригодным для решения поставленной задачи, потому что операция, которую требуется осуществить над этой функцией, трудновыполнима или невыполнима совсем. Например, вычисление значения трансцендентной функции «вручную». Действительно, чтобы вычислить , проще всего воспользоваться степенным разложением функции, т.е. заменить трансцендентную функцию степенным рядом. При этом получается приближенное значение функции.

Другая ситуация, когда может потребоваться аппроксимация аналитически заданной функции – дифференцирование функции, вычисление определенных и неопределенных интегралов. Если аналитическое выражение функции достаточно сложное, то поставленная задача трудно выполнима, а иногда и невыполнима с помощью элементарных приемов. Например, интеграл существует, но по формуле Ньютона-Лейбница практически вычислен быть не может, т.к. первообразная не выражается в элементарных функциях. Аппроксимация подынтегральной функции – один из возможных приемов.

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

Для оценки «близости» функций выбирают тот или иной критерий согласия. Эти критерии основаны на использовании той или иной метрики, т.е. способа введения расстояния между функциями, принадлежащими тому или иному классу: . Например, для функций, ограниченных на отрезке , расстояние может быть введено следующим образом: ; для функций, непрерывных на отрезке , по формуле .

Часто процедура аппроксимации связана с другим критерием согласия:

.

Применяемый на его основе способ аппроксимации получил название метода наименьших квадратов.

Для функций, заданных таблично, достаточно распространенным критерием согласия является критерий Чебышева, который определяет расстояние между аппроксимируемой и аппроксимирующей функциями как максимум величины отклонения между этими функциями в узлах сетки:

.

Если , т.е. , то соответствующий способ аппроксимации называют интерполяцией, а процедуру вычисления значений с помощью в точках, не являющихся узлами сетки, - интерполированием.

Задача интерполирования состоит в следующем.

На отрезке заданы точки , которые называются узлами интерполяции, и значения некоторой функции в этих точках:

. (5.1)

Необходимо построить функцию - интерполирующую функцию, принадлежащую некоторому классу и принимающую в узлах интерполяции заданные значения (5.1), т.е.

. (5.2)

Геометрически это означает, что нужно найти кривую определенного типа, проходящую через заданные точки .

В такой общей постановке задача может иметь бесконечное множество решений или совсем их не иметь.

Сформулированная задача становится однозначной, если вместо произвольной функции искать полином степени не выше , удовлетворяющий условиям (5.2), т.е.

.

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

Различают интерполирование в узком смысле, т.е. когда , и экстраполирование, т.е. когда . В дальнейшем, под термином интерполирование будет пониматься как первая, так и вторая операции.

§5.2. Конечные разности. Обобщенная степень.

Пусть задана функция . Обозначим через фиксированную величину приращения аргумента (шаг). Тогда выражение

                        (5.3)

называется первой конечной разностью функции . Аналогично определяются конечные разности высших порядков

Например:

   (5.4)

Символ (дельта) можно рассматривать как оператор, ставящий в соответствие функции функцию .

Легко проверить основные свойства оператора :

1) ;

2) ;

3) , где (целые неотрицательные числа), причем .

Из формулы (5.3) имеем:

.

Отсюда, рассматривая как символический множитель, получим:

.                               (5.5)

Из формулы (5.4):

;                    (5.6)

и т.д. Окончательно получим:

.                           (5.7)

В дальнейшем нам понадобится понятие обобщенной степени.

Определение.

Обобщенной -степенью числа называется произведение сомножителей, первый из которых равен , а каждый следующий на меньше предыдущего:

,                 (5.8)

где .

Полагают, что . При обобщенная степень совпадает с обычной: .

Вычислим конечные разности для обобщенной степени, полагая . Для первой конечной разности имеем:

то есть

.                                      (5.9)

Для второй конечной разности:

,

то есть

.                              (5.10)

Аналогично,

,

и так далее.

Окончательно будем иметь:

,                    (5.11)

, если .                                                        (5.12)
§5.3. Первая интерполяционная формула Ньютона.
Пусть для функции заданы значения для равноотстоящих значений независимой переменной , где - шаг интерполяции. Требуется подобрать полином степени не выше , принимающий в точках значения

.                                          (5.13)

Условия (5.13) эквивалентны тому, что

.                              (5.14)

Будем искать полином в виде

.                            (5.15)

Используя понятие обобщенной степени, запишем выражение (5.15) в виде:

.      (5.16)

Чтобы полином был определен, нужно найти коэффициенты . Полагая в выражении (5.16), получим

.                                         (5.17)

Чтобы найти коэффициент , составим первую конечную разность:

.

Полагая , получим:

,

откуда

.                                              (5.18)

Для определения коэффициента составим вторую конечную разность:

.

Положив , получим:

,

откуда

.                                            (5.19)

Продолжая процесс, получим:

,                               (5.20)

причем .

Подставляя найденные значения коэффициентов в выражение (5.16), получим интерполяционный полином Ньютона:

. (5.21)

Этот полином полностью удовлетворяет требованиям поставленной задачи. Действительно, степень полинома не выше ; ;

Для практического использования первую интерполяционную формулу Ньютона записывают в несколько преобразованном виде. Для этого введем новую переменную

.                                                 (5.22)

Тогда

      (5.23)

Подставляя (5.23) в (5.21), получим окончательный вид первой интерполяционной формулы Ньютона:

. (5.24)

Если в формуле (5.24) положить , то получим формулу линейного интерполирования:

.                                        (5.25)

При получим формулу параболического или квадратичного интерполирования:

.                        (5.26)

Первую интерполяционную формулу Ньютона используют для интерполирования функции в окрестности начальной точки , где мало по абсолютной величине и представляет собой число шагов, необходимых для достижения точки , исходя из точки .

Остаточный член первой интерполяционной формулы Ньютона:

,                         (5.27)

где - некоторое промежуточное значение между узлами интерполирования и рассматриваемой точкой .

Учитывая, что , приближенно можно положить:

.

В этом случае соотношение (5.27) примет вид:

.                       (5.28)
§5.4. Вторая интерполяционная формула Ньютона.
Вторая интерполяционная формула Ньютона применяется для интерполирования в окрестности конечного значения .

Пусть для функции заданы значения для равноотстоящих значений независимой переменной . Построим полином следующего вида:

             (5.29)

Используя обобщенную степень, получим:

.    (5.30)

Найдем коэффициенты из условий . Эти условия равносильны

.                             (5.31)

Полагая в выражении (5.30), получим

.                                         (5.32)

Чтобы найти коэффициент , составим первую конечную разность:

.

Полагая , получим:

.

Отсюда

.                                           (5.33)

Из второй конечной разности

при находим:

.

Следовательно,

.                                        (5.34)

Продолжая дальнейшее вычисление конечных разностей, получим:

.                            (5.35)

Подставляя найденные значения коэффициентов в выражение (5.29), получим вторую интерполяционную формулу Ньютона:

           (5.36)

Введем новую переменную

,                                                 (5.37)

тогда

                        (5.38)

С учетом (5.38) вторая интерполяционная формула Ньютона примет вид:

. (5.39)

Остаточный член второй интерполяционной формулы Ньютона:

, (5.40)

где - промежуточное значение между узлами интерполирования и точкой .

§5.5. Интерполяционная формула Лагранжа.

Пусть на отрезке задана произвольная система точек , в которых известны значения функции . То есть, задана следующая таблица

Таблица 5.1.

			…
			…

Установим зависимость одного ряда чисел от другого и построим новую функцию, которая с определенной степенью точности будет приближена к заданной.

Построим многочлен таким образом, чтобы его значения совпали со значениями функции, заданными в таблице, для тех же аргументов, то есть

.                                           (5.41)

Лагранж предложил строить многочлен -й степени в виде:

    (5.42)

Здесь в каждом слагаемом отсутствует скобка , которой соответствует коэффициент .

Найдем неизвестные коэффициенты , называемые коэффициентами Лагранжа, используя условие (5.41).

При : .

.

Следовательно, коэффициент вычисляется по следующей формуле:

.

При : .

.

Следовательно, коэффициент вычисляется по следующей формуле:

.

Таким образом, коэффициенты вычисляются по формулам:

.

С учетом найденных коэффициентов интерполяционный полином Лагранжа запишется в виде

.                (5.43)

Для интерполяционной формулы Лагранжа справедлива оценка погрешности:

,           (5.44)

где .

Пример 5.1. По заданной системе точек

Таблица 5.2.

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

.

Коэффициенты этого многочлена будут вычислены по следующим формулам:

,

,

.

Тогда многочлен Лагранжа второго порядка будет иметь вид:

Учитывая, что таблица приведена для функции , вычисленной в узловых точках , сравним погрешность вычислений данной функции и построенного многочлена в контрольной точке :

и .

Погрешность вычислений равна

.

Ниже приведены графики функции и построенного полинома Лагранжа на заданном интервале. Из рисунка 5.1 видно, что многочлен второго порядка обеспечивает достаточно высокую точность построения синусоиды на заданном отрезке .

Рис.5.1.

Если таблица 5.1, для которой построена формула Лагранжа, задана для равноотстоящих узлов , то формула Лагранжа упрощается. Обозначим через . Тогда

,

,…,

.

С учетом введенных обозначений формула Лагранжа запишется так:

Запишем формулу Лагранжа в случае, если :

Получили формулу линейной интерполяции (5.25):

.

Здесь - табличные разности первого порядка.

При получаем формулу квадратичной интерполяции (5.26):

.

Здесь - табличные разности второго порядка, и так далее. Продолжая этот процесс, окончательно получим:

.

Эта формула называется первой интерполяционной формулой Ньютона (сравните с формулой (5.24)). Для нее справедлива оценка остаточного члена (5.27) и (5.28).

Если обозначить через , то с учетом введенного обозначения, получим:

, …,

.

Тогда формула (5.43) примет вид:

.

Эта формула называется второй интерполяционной формулой Ньютона (сравните с формулой (5.39)). Для нее справедлива оценка остаточного члена (5.40).

§5.6. Метод наименьших квадратов для обработки результатов экспериментов.

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

.

Используем для построения результаты эксперимента:

Таблица 5.3

			…
			…

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

Используя вид , получим:

.

Необходимыми условиями экстремума функции является равенство нулю ее первой производной по всем переменным . Расписав эти условия, получим СЛАУ вида:

Запишем систему для определения в нормальной форме:

Решим систему одним из известных методов и найдем коэффициенты , которые затем подставим в искомый многочлен.

Запишем алгоритм метода наименьших квадратов.

1.     Ввести таблицу чисел .

2.     Вычислить .

3.     Решить любым известным методом полученную систему линейных алгебраических уравнений и получить коэффициенты искомого многочлена .

Пример 5.2. По заданной системе точек (см. Табл.5.3) из примера 5.1 построить аппроксимационные многочлены первого и второго порядков методом наименьших квадратов.

Для построения полинома первого порядка необходимо вычислить следующие суммы

,

и решить СЛАУ относительно неизвестных коэффициентов вида:

Значения неизвестных коэффициентов равны:

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

.

Погрешность вычислений по данной формуле в контрольной точке составляет

.

Для построения многочлена второго порядка дополнительно необходимо вычислить следующие суммы

,

и решить СЛАУ относительно неизвестных коэффициентов вида:

Значения неизвестных коэффициентов равны:

.

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

.

На рисунке 5.2 приведены графики искомых полиномов и табличной функции. Погрешность вычислений по данной формуле в контрольной точке равна:

.

Рис.5.2.
§5.7.
Обработка экспериментальных данных некоторыми другими
функциями.
Во многих случаях экспериментальные данные могут быть аппроксимированы не только полиномами различных порядков. Это обусловлено физическими, экономическими и другими законами исследуемых процессов, а также опытом испытателя. Если, например, испытатель уверен, что параметры какого-либо прибора, снятые с испытательного стенда, по своим физическим характеристикам являются близкими к экспоненциальным, то нет смысла аппроксимировать их полиномами. Также экспериментальные данные могут быть аппроксимированы показательными, логарифмическими, тригонометрическими и другими функциями.

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

Сформулированную задачу будем решать методом наименьших квадратов. Функция в этом случае запишется так:

.

Расписав необходимые условия экстремума этой функции по переменным и , и, сделав несложные преобразования, получим СЛАУ второго порядка вида:

Решая эту систему любым известным методом, определим коэффициенты экспоненциальной функции и .

Пример 5.3. По заданной в таблице 5.4 системе точек

Таблица 5.4.

	0	0,7	1,39	1,65	1,93	2,2	2,45	2,79
	0,05	0,07	0,24	0,42	0,66	0,78	0,89	1,07

методом наименьших квадратов построить аппроксимационную экспоненциальную функцию вида:

.

Для построения необходимо вычислить следующее суммы:

, , , ,

и решить СЛАУ второго порядка относительно неизвестных коэффициентов и :

Значения неизвестных коэффициентов равны: , .

Тогда искомая экспоненциальная функция будет иметь вид:

.

График функции и ломаная , построенная по результатам, приведенным в таблице 5.4, изображены на рисунке 5.3.

Рис.5.3.

Bukvasha