Быстрый поиск

Курсовая работа: Методы решения алгебраических уравнений

Таблица 4.1

x	x0	x1	x2	…	x1	…	xn
F(x)	Y0	Y1	Y2	…	Y1	…	yn

Повод для аппроксимации может возникнуть даже тогда, когда аналитическое выражение для некоторой функции y = F(x) имеется. однако оно оказывается мало пригодным для решения поставленной задачи, потому что операция, которую требуется осуществить над этой функцией, трудновыполнима. Элементарный пример - вычисление значения трансцендентной функции «вручную». Действительно, чтобы вычислить , например, In 3,2756, проще всего воспользоваться степенным разложением функции, т.е. заменить трансцендентную функцию степенной. При этом получится, разумеется, приближенное значение функции, но если мы умеем контролировать погрешность, то можно считать, что мы получили интересующий нас результат хотя бы потому, что в реальности все равно приходится ограничиваться приближенным представлением значений логарифмической функции.

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

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

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

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

(см. гл. 2).

Например, для функций, ограниченных на отрезке [a,b] расстояние может быть введено следующим образом:

(F(x),G(x))= ;

для функций, непрерывных на отрезке [a,b], по формуле

2dx

(а также многими другими способами).

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

(4.1)

Если =0, т.е. F(xi)=G(xi)=yi, то соответствующий способ аппроксимации называют интерполяцией, а процедуру вычисления значений F(x) с помощью G(x) в точках, не являющихся узлами сетки, - интерполированием.

С геометрической точки зрения график функции G(x) при интерполировании должен проходить через все точки A0(x0,y0), A1(x1,y1),…, An(xn,yn). Подчеркнем, что для значений x, не являющихся узловыми, значения функции G(x) ничем не регламентированы, и в принципе могут значительно отличаться от значений функций F(x)).

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

(4.2)

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

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

Полином Лагранжа.

Пусть Функция F(x) задана табл. 4.1. Построим многочлен Ln (x), степень которого не выше, чем n, и для которого выполнены условия интерполяции

Ln(x0)=y0, Ln(x1)=y1,…, Ln(xn)=yn. (4.6)

Будем искать Ln (x) в виде

Ln (x),=l0(x)+l1(x)+…+ln(x), (4.7)

где l1(x) – многочлен степени n, причем

l1(xл)= (4.8)

Очевидно, что требование (4.8) с учетом (4.7) вполне обеспечивает выполнение условий (4.6).

Многочлены l1(x)составим следующим образом:

l1(x)=Сi(x - x0)(x - x1)(xi - xi-1)(xi xi=1) (xi – xn) (4.9)

где Ci – коэффициент, значение которого найдем из первой части условия (4.8):

Сi =

(заметим, что ни один множитель в знаменателе не равен нулю). Подставим Ci в (4.9) и далее с учетом (4.7) окончательно имеем:

Ln (x)= (4.10)

Это и есть интерполяционный многочлен Лагранжа. По таблице исходной функции F формула (4.10) позволяет довольно просто составить «внешний вид» многочлена.

Метод наименьших квадратов.

1) На практике часто приходится решать такую задачу. пусть для двух функционально связанных величин x и y известны n пар соответствующих значений (x1,y1),(x2,y2),…,(xn,yn). Требуется в наперед заданной формуле y=f(x, a1, a2,…,am) определить m параметров a1, a2, …,am (m<n) так, чтобы в эту x и y.

Считается (исходя из принципов теории вероятностей), что наилучшими являются те значения a1, a2, …,am, которые обращают в минимум сумму

(т.е. сумму квадратов отклонений значений y, вычисленных по формуле, от заданных), поэтому сам способ и получил название способа наименьших квадратов.

Это условие дает систему m уравнений, из которых определяются a1,a2,…,am:

(1)

(f=1,2,…, m).

На практике заданную формулу y=f (xk,a1, a2, , am) иногда приходится (в ущерб строгости полученного решения) преобразовывать к такому виду, чтобы систему (1) было проще решать (см. ниже подбор параметров в формулах y=Aecx и y=Axq). Частные случаи: а) y=a0xm-1+…+ am(m+1 параметров a0, a1, …, am;; n>m+1).

Система (1) принимает следующий вид:

(2)

Эта система m+1 уравнений с m+1 неизвестными всегда имеет единственное решение, так как ее определитель отличен от нуля.

Для определения коэффициентов системы (2) удобно составить вспомогательную таблицу

В последней строке записывают сумму элементов каждого столбца, которые и являются коэффициентами системы (2).

Систему (2) обычно решают методом Гаусса.

б) y=Aecx.

Для упрощения системы (1) эту формулу, связывающую х и у, предварительно логарифмируют и заменяют формулой

1g y=1g .

Система (1) примет в этом случае следующий вид:

(3)

Вспомогательная таблица имеет вид

Из систему (3) определяют с и 1g A.

в) y=Axq.

Эту формулу также предварительно логарифмируют и заменяют следующей:

Система (1) теперь примет вид

(4)

Соответствующим образом изменяется и вспомогательная таблица.

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

Необходимые условия минимума этого интеграла приводят к системе m+1 уравнений с m+1 неизвестными a0, a1, a2,..., am, из которых определяют все эти коэффициенты:

(5)

4. Численные методы решения обыкновенных дифференциальных уравнений. Метод Эйлера. Метод Рунге – Кутта

1. Метод Эйлера. Дифференциальное уравнение y’=f(x, y) определяет на плоскости так называемое поле направлений, т.е. в каждой точке плоскости, в которой существует функция f(x, y) задает направление интегральной кривой уравнения, проходящей через эту точку. Пусть требуется решить задачу Коши, т.е. найти решение уравнения y’=f(x, y), удовлетворяющее начальному условию y(x0)=y0. Разделим отрезок [x0, X] на n равных частей и положим (X-x0)/n=h (h – шаг изменения аргумента).Допустим, что внутри элементарного промежутка от x0 до x0+h функция y’ сохраняет постоянное значения f(x0,y0,). Тогда где y1 значения искомой функции, соответствующее значению х1=x0+h. Отсюда получаем Повторяя эту операцию, получим последовательные значения функции:

Таким образом, можно приближенно построить интегральную кривую в виде ломаной с вершинами Mr (xr; yr), где Этот метод называется методом ломаных Эйлера, или просто методом Эйлера.

2. Метод Рунге – Кутта. Пусть функция у определяется дифференциальным уравнением y’=f(x, y) при начальном условии y(x0)=y0. При численном интегрировании такого уравнения методом Рунге – Кутта определяют четыре числа: