Метод простой итерации. В основе метода заложено понятие сжимающего отображения

В основе метода заложено понятие сжимающего отображения. Определим терминологию:

Говорят, что функция осуществляет сжимающее отображение на , если

1.

2.

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

Теорема Банаха (принцип сжимающих отображений).
Если — сжимающее отображение на , то:

1. — корень;

2. итерационная последовательность сходится к этому корню;

для очередного члена справедливо Поясним смысл параметра . Согласно теореме Лагранжа имеем:

Отсюда следует, что . Таким образом, для сходимости метода достаточно, чтобы

1.

и так далее, пока

1) Интерполяция.

Интерполя́ция в математике и статистике, отыскание промежуточных значений величины по некоторым известным её значениям

Необходимо получить многочлен Pn(x) такой, чтобы выполнялось условие:

Pn(xi)=yi. (42)

Для этого зададимся конкретным видом многочлена. Пусть Pn(x) имеет следующий вид:

Pn(xi)=a0+a1x+a2x2+…+anxn. (43)

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

(44)

Полином с коэффициентами, полученными путём решения системы (44) называют интерполяционным полиномом Лагранжа и обозначают Ln(x). Решение системы (44) весьма трудоёмко, поэтому интерполяционный полином Лагранжа представляют в виде линейной комбинации многочленов степени n:

. (45)

Необходимо, чтобы каждый многочлен li(x) обращался в нуль во всех узлах интерполяции, за исключением i-го, в котором он равен 1 (Рис. 12). Если li(x) удовлетворяет таким условиям, то в i-ом узле интерполяции многочлен Ln(x) примет значение yi, что удовлетворяет условию поставленной задачи. Таким условиям удовлетворяет многочлен вида:

. (46)

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

(47)

2) Приближенное вычисление интегралов: метод прямоугольников, метод трапеций, метод Симпсона.

Численные методы вычисления определённых интегралов

Метод левых прямоугольников

Эти методы численного интегрирования основываются на геометрическом смысле интеграла. Как известно интеграл есть площадь криволинейной трапеции ограниченной подынтегральной функцией f(x) на отрезке [a,b]. Для вычисления интеграла I отрезок [a,b] разбивают на n отрезков длиной h. На каждом отрезке криволинейную трапецию приближают прямоугольником, так как его площадь можно легко вычислить. Затем суммируют все полученные площади, получая тем самым приближённое значение интеграла. Его название объясняется тем, что высота прямоугольника f(x) вычисляется в левой границе отрезка h. приближённое значение интеграла, полученное этим методом, вычисляется по формуле:

Метод правых прямоугольников

Этот метод похож на предыдущиу. Отличие в том, что высота прямоугольников вычисляется по правой границе . Метод средних прямоугольников

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

Метод трапеций

Метод трапеций основан на том, что криволинейная трапеция приближается прямолинейной (Рис. 8). Т.е. площади вычисляются по следующей формуле:

Таким образом, получаем общую формулу трапеций:
. (35)

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

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

Геометрически это выглядит так:

Формула метода Симпсона (парабол) имеет вид

.

Абсолютная погрешность метода Симпсона оценивается как

51) Численные методы решения обыкновенных дифференциальных уравнений первого порядка: метод Эйлера, методы Рунге-Кутта

Метод Эйлера для решения начальной задачи (2.1.1) был описан Эйлером в 1768 году. Этот метод весьма прост. Его глобальная погрешность имеет вид , где – постоянная, зависящая от задачи, и – максимальная длина шага. Если желательно, скажем, получить 6 точных десятичных знаков, то требуется, следовательно, порядка миллиона шагов, что не слишком удовлетворительно. С другой стороны, еще со времен Ньютона известно, что можно найти гораздо более точные методы, если не зависит от , то есть если мы имеем задачу (2.1.1), решаемую квадратурой

. (2.2.1)

Общая формулировка методов Рунге-Кутты

Рунге и Хойн построили новые методы, включив в указанные формулы один или два добавочных шага по Эйлеру. Но именно Кутта сформулировал общую схему того, что теперь называется методом Рунге-Кутты.

Пусть – целое положительное число (число стадий, этапов) и – вещественные коэффициенты. Тогда метод

(2.3.1)

называется -стадийным явным методом Рунге-Кутты для исходной задачи Коши (2.1.1)

Обычно коэффициенты удовлетворяют условиям

. (2.3.2)

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

Метод Рунге-Кутты имеет порядок , если для достаточно гладких задач (2.1.1) справедливо неравенство

, (2.3.3)

то есть ряды Тейлора для точного решения и для совпадают до члена включительно.

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

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

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

Пусть задана некоторая (параметрическая) модель вероятностной (регрессионной) зависимости между (объясняемой) переменной y и множеством факторов (объясняющих переменных) x

где — вектор неизвестных параметров модели

— случайная ошибка модели.

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

тров b можно рассчитать теоретические (модельные) значения объясняемой переменной y:

Тогда можно рассчитать остатки регрессионной модели — разницу между наблюдаемыми значениями объясняемой переменной и теоретическими (модельными, оцененными):

Величина остатков зависит от значений параметров b.