Метод деления отрезка пополам

В отличие от предыдущего метода метод гарантированно дает корень, если он имеется на заданном отрезке [a,b]. Суть метода показана на рис. 1.68. В качестве исходных данных задается отрезок [a,b] с корнем внутри его. Вычисляется функция fa = f(a). Отрезок [a,b] делится пополам точкой c = (a + b) / 2. Вычисляется функция fc = f(c). Далее проверяются знаки fa и fc. Если эти величины имеют одинаковые знаки, то точка a переносится в точку c:

a = с, fa = fc

.Если fa и fc имеют разные знаки, то точка b переносится в точку с: b = c. Далее процесс сужения отрезка [a,b] продолжается до тех пор, пока b – a не станет меньше заданной погрешности. Корень при этом в точке с.

Метод деления отрезка пополам - student2.ru

Рис. 1.68. Суть метода деления отрезка пополам

Метод Ньютон

Суть метода показана на рис. 1.69. В качестве начального приближения в методе задается значение x0. Метод используется тогда, когда производная функции f(x) определена в аналитическом виде.

В точке x0 вычисляется значение функции f0 = f(x0). Далее по формуле

x1 = x0 – f0 / f’(x0) (2)

вычисляется точка x1 пересечения касательной, проведенной из точки f0. Если |x1 x0|>E (E —заданная погрешность), то полагается x0 = x1, вычисляется f0 = f(x0) и итерационный процесс по формуле (2) продолжается до тех пор, пока не окажется |x1 – x0| < E. Корень при этом в x1. Метод Ньютона не гарантирует сходимость алгоритма к корню.

Метод деления отрезка пополам - student2.ru

Рис. 1.69. Суть метода ньютона

Метод Вегстейна

Метод является модификацией метода Ньютона и используется для функций, у которых неизвестна в аналитическом виде производная f’(x0). Суть метода показана на рис. 1.70.

В качестве начального приближения в методе задается два начальных приближения x0 и x1. Желательно эти начальные приближения задавать по разную сторону от корня. Далее вычисляются значения функции f0 и f1 и через точки f0 и f1 проводится секущая до пересечения ее с осью Х в точке x2:

x2 = x0 – (f0(x0 – x1) / (f0 – f1)) (3)

Далее вычисляется значение функции f2. Если |x2 – x0| > E (E —погрешность), то полагается

x0 = x1 , x1 = x2, f0 = f1, f1 = f2

и итерационной процесс по формуле (3) продолжается до тех пор, пока не окажется |x2 – x0| < E. Метод Вегстейна практически всегда сходится к корню.

Метод деления отрезка пополам - student2.ru

Рис. 1.70. Суть метода Вегстейна

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

Во всех методах исходный отрезок [a,b] разбивается на более мелкие интервалы длиной h. Величина шага h определяется точностью вычисления интеграла.

Метод средних

Суть метода показана на рис. 1.71.

В этом методе площадь, ограниченная кривой f(x) заменяется площадью прямоугольника fi * h, где fi = f(xi + h / 2). В общем случае интеграл по формуле средних определяется формулой:

Метод деления отрезка пополам - student2.ru

Метод деления отрезка пополам - student2.ru

Рис. 1.71. Суть метода средних

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

Суть метода показана на рис. 1.72.

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

Метод деления отрезка пополам - student2.ru

Метод деления отрезка пополам - student2.ru

Рис. 1.72. Суть метода трапеций

Метод Симпсона

Суть метода показана на рис. 1.73.

В этом методе площадь, ограниченная кривой f(x) заменяется площадью, ограниченной параболой, где xi+1/2=(xi + xi+1) / 2. В общем случае интеграл по формуле Симпсона определяется формулой:

Метод деления отрезка пополам - student2.ru

Метод деления отрезка пополам - student2.ru

Рис. 1.73. Суть метода Симпсона

Аппроксимация функций

В качестве исходных данных аппроксимации задается таблично заданная функция fi для дискретного набора аргументов xi, Метод деления отрезка пополам - student2.ru . При аппроксимации известна кривая, которая должна покрывать набор табличных значений. У этой кривой f(a,x) неизвестны только параметры a, которые обеспечивают оптимальное расположение кривой f(a,x) относительно табличных данных. Подбор параметров а осуществляется по методу наименьших квадратов, в соответствии с которым:

Метод деления отрезка пополам - student2.ru

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

Метод деления отрезка пополам - student2.ru

Очень часто используется линейная аппроксимация:

Метод деления отрезка пополам - student2.ru

В этом случае нелинейная система уравнений преобразуется к линейной

Метод деления отрезка пополам - student2.ru

где: Метод деления отрезка пополам - student2.ru

Метод деления отрезка пополам - student2.ru

Для решения данной задачи необходимо решить систему линейных алгебраических уровнений относительно aj .В случае представления f(a,x) набором ортогональных функций Метод деления отрезка пополам - student2.ru матрица Метод деления отрезка пополам - student2.ru сводится к диагональному виду, так как Метод деления отрезка пополам - student2.ru =0 для i≠k. Для ортогональных Метод деления отрезка пополам - student2.ru величина ak определяется выражением:

Метод деления отрезка пополам - student2.ru

Очень часто аппроксимируемая функция f(a,x) называется линией тренда. В частности, в Excel существует сервис получения линий тренда для фиксированного набора функций f(a,x). Приведем пример получениялинии тренда в среде Excel. Прежде всего необходимо задать табличные значения функции Метод деления отрезка пополам - student2.ru с х в 1-й строке и f во второй строке (рис. 1.74).

Метод деления отрезка пополам - student2.ru

Рис. 1.74. Исходная функциональная зависимость

По этим даны далее необходимо построить точечный график. Для этого выделяем исходные данные (рис. 1.74) в выбираем меню Вставка | Диаграмма.В процессе диалога Мастера(рис. 1.75) выбираем точечную диаграмму и далее (рис. 1.76) заполняем поля надписей диаграммы.

Метод деления отрезка пополам - student2.ru

Рис. 1.75. Окно Мастера для выбора типа диаграммы

В конце диалогового режима с Мастеромбудет построен точечный график (рис. 1.77).

Метод деления отрезка пополам - student2.ru

Рис. 1.76. Заполнение полей надписей диаграммы

Метод деления отрезка пополам - student2.ru

Рис. 1.77. Построенный точечный график

Для построения линии тренда необходимо подвести указатель мыши на любую точку графика, что бы высветилась всплывающая подсказка (рис. 1.78) и далее правой клавиши мыши вывести контекстное меню (рис. 1.79). В контекстном меню выбрать пункт Добавить линию тренда.Из предложенных вариантов линий тренда выбрать полиномиальную степени 2 (рис. 1.80). В результате на имеющемся уже точечном графике будет построена оптимальная для этих точек линия тренда (рис. 1.81).

Метод деления отрезка пополам - student2.ru

Рис. 1.78. Всплывающая подсказка

Метод деления отрезка пополам - student2.ru

Рис. 1.79. Контекстное меню

Метод деления отрезка пополам - student2.ru

Рис. 1.80. Из предложенных линий выбираем полиномиальную

Метод деления отрезка пополам - student2.ru

Рис. 1.81. Построенная линия тренда

Интерполяция функции

В качестве исходных данных при интерполяции задается таблица (fi,xi). Задачей интерполяции является восстановление значений функции при любом значении x по узлам табличных значений. Наиболее простым методом является линейная интерполяция, суть которой демонстрирует рис. 1.82.

Метод деления отрезка пополам - student2.ru

Рис. 1.82. Суть линейной интерполяции

Несложно показать геометрически, что при линейной интерполяции значение f в точке x определяется выражением:

Метод деления отрезка пополам - student2.ru

при условии, что xi≤x≤xi+1.

Более точной является квадратичная интерполяция, суть которой продемонстрирована на рис. 1.83.

Метод деления отрезка пополам - student2.ru

Рис. 1.83. Суть квадратичной интерполяции

Несложно показать геометрически, что при квадратичной интерполяции значение f в точке x определяется выражением:

Метод деления отрезка пополам - student2.ru

при условии, что |x-xi|=min для всех Метод деления отрезка пополам - student2.ru .

Наши рекомендации