- •Министерство образования и науки Российской федерации
- •Кафедра математики и математических методов в экономике
- •ЧИСЛЕННЫЕ МЕТОДЫ
- •Хабаровск 2014
- •1.1. Постановка задачи о приближении функций
- •1.2. Метод множителей Лагранжа
- •Идея метода – искать полином не в виде (1.2), а как
- •Схема построения полиномов Лагранжа
- •Шаг 2. Пусть x – переменная. Составим произведение
- •Шаг 3. Раскрывая внешние скобки, можно получить многочлен степени n
- •Пример. По таблице
- •Шаг 1. Находим коэффициенты
- •Шаг 3. Раскрыв скобки, получим
- •1.3. Метод разделённых разностей и полиномы Ньютона
- •Часть 1. Разностные аналоги производных
- •Часть 2. Рекурсивное вычисление функции
- •Пример. Известна таблица значений функции
- •Ответ: значения полинома Ньютона равны 18 в точке 2 и 2,2401 в точке 0,7.
- •Аналогично
- •Продифференцировав каждое слагаемое три раза, получим
- •1.5. Метод наименьших квадратов
- •Поиск линейной зависимости
- •Подставив суммы в систему (1.11), получим
- •Подставив найденные суммы в систему (1.12), получим
- •Пример 4. По приведённым данным
- •Отсюда очевидным образом имеем, что
- •Схема метода касательных
- •Вычисление корней при помощи метода простых итераций
- •Составим систему
- •Соответствующая линейная система имеет вид
- •Таблица 2.3 – Решение примера 2
- •Общая схема метода
- •Остаётся сравнить значения
- •Общая схема метода золотого сечения
- •Пусть функция f(x) задана таблицей
- •Проинтегрировав, получаем, что
- •Последовательно находим
- •Интегрируя каждое слагаемое, получим, что
- •Тогда интеграл сводится к
- •Проинтегрировав каждое слагаемое, получим
- •По теореме об интегрировании сходящихся степенных рядов
- •Если интеграл определённый, то
- •Найдём значения
- •По формуле трапеций получим
- •По формуле Симпсона будет
- •По формуле парабол
- •Поскольку значения на концах не зависят от числа точек и
- •Ответ:
- •Шаг 4. Ответ:
- •Тогда
- •Ответ:
- •Ответ:
- •Формула метода 3-го порядка точности:
- •Ответ:
- •Формула метода 4-го порядка точности
- •Все дальнейшие вычисления аналогичны и приведены в таблице.
- •Таблица (начало)
- •Таблица (окончание)
- •Ответ:
- •Пример 1. Решим систему
- •Ответ:
- •Последнее преобразуется к виду
- •Задачу (5.10) – (5.11) будем записывать в виде операторного уравнения
- •Из ограниченности третьей производной следует, что
- •Таким образом, точность близости будет О(h).
- •В силу граничных условий имеет место и неравенство
- •Если yh есть решение уравнения (5.12), то из (5.27) имеем оценку
- •Замечание о делении отрезка на части
- •Решение уравнений делением отрезка
- •Метод секущих (хорд)
- •При реализации в EXCEL достаточно заполнить строчку
- •Метод касательных
- •Реализация метода мало отличается от метода секущих, заполняем строку
- •Таблица 6.1 – Решение уравнения
- •Подбор полиномов, проходящих через точки
- •Таблица 6.2 – Поиск полинома при помощи обратной матрицы
- •Полиномы Лагранжа
- •Таблица 6.3 – Построение полинома Лагранжа
- •Таблица 6.4 – Построение полинома Ньютона
- •Метод Эйлера решения задачи Коши
- •Таблица 6.5 – Решение уравнения методом Эйлера
- •Приближённое интегрирование
- •Таблица 6.6 – Вычисление интеграла методом трапеций и методом Симпсона
- •ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
- •Часть 1. Задания для работы без пакетов прикладных программ
- •Задание 1. Решение уравнений
- •Задание 2. Метод простых итераций
- •Задание 3. Метод простых итераций в приближённых вычислениях
- •Задание 4. Полиномы Лагранжа и Ньютона
- •Задание 5. Метод наименьших квадратов
- •Задание 6. Приближённое интегрирование
- •Задание 7. Задача Коши
- •Часть 2. Задания для работы в пакете EXCEL
- •Задание 1. Приближение функций полиномами
- •Задание 2. Задача Коши
- •Задание 3. Системы дифференциальных уравнений
- •Задание 4. Задача Коши 2-го порядка
- •Задание 5. Приближённое интегрирование
- •Задание 7. Метод Ньютона решения систем нелинейных уравнений
- •Задание 9. Применение рядов в приближённом интегрировании
- •Оглавление
f a f d , или к точке b, если f a f d . Будет получено наименьшее значение, не являющееся локальным минимумом (глобальный минимум).
Общая схема метода
Даны отрезок [a, d] и f x . Надо найти точку глобального минимума xmin
сточностью .
1)Найдём b a d a / 3 и c a 2 d a / 3 .
2) |
Если c b , то xmin b при f b f c и xmin c при |
f b f c , а вычис- |
|
ления прекращаем; если же c b , переходим к п.3). |
|
|
|
3) |
Если f b f c , то a a и d c ; иначе (если |
f b f c ) делаем a b и |
dd .
4)Переходим к п.1.
Здесь равенства подразумеваются как операторы присваивания.
Если поменять всюду знаки неравенств, то в процессе вычислений придём к точке максимума xmax . В случае f b f c можно оставить любую часть – или
[a, c], или [b, d]. Для компьютера числа с плавающей запятой типа REAL никогда не равны, и результат выбора будет случаен.
Метод прост, но сходится очень медленно – ещё медленнее, чем метод деле-
ния отрезка. Для достижения точности необходимо log |
|
d a |
приближений, |
|
1,5 |
|
|||
|
|
|||
|
|
|
где d a – длина начального отрезка.
Пример. Найдём с точностью 0,1 точку глобального минимума функции f x x2 x на отрезке 0; 1 . Вычисления проведём с одной запасной цифрой.
1-й шаг. Длина отрезка 0; 1 равна 1, треть длины равна 1/3. Отрезок делится на три части точками a 0, b 0,33, c 0,67, d 1 .
Находим f 0,33 0,332 0,33 0,22 и f 0,67 0,672 0,67 0,22 .
Поскольку f 0,33 f 0,67 , можно взять как 0; 0,67 , так и 0,33; 1 .
2-й шаг. Возьмём отрезок 0; 0,67 . Треть его длины равна 0,22, поэтому те-
перь a 0, b 0,22, c 0,45, |
d 0,67 . Находим |
|
f 0,22 0,222 |
0,22 0,17 и |
f 0,45 0,452 0,45 0,25. |
|
49 |
|
Поскольку f 0,22 f 0,44 , оставляем участок 0,22; 0,67 как новый отрезок.
3-й шаг. Теперь a 0,22, b 0,37, |
c 0,52, d 0,67 . Считаем |
||
f 0,37 0,372 0,37 0,23 и |
f 0,52 0,522 0,52 0,25 . |
||
Так как f 0,37 f 0,52 , остаётся отрезок 0,37; |
0,67 . |
||
4-й шаг. Для точек a 0,37, b 0,47, c 0,57, |
d 0,67 замечаем, что |
||
c b 0,57 0,47 0,1 . |
|||
Остаётся сравнить значения |
|
|
|
f 0,47 0,472 0,47 0,25 |
и |
f 0,57 0,572 0,57 0,245 . |
Поскольку f 0,47 f 0,57 , считаем, что xmin 0,47 0,5 . Ответ: xmin 0,5 с точностью 0,1.
Легко видеть, что точка x = 0,5 – точное решение задачи как вершина параболы y x 2 x . Поэтому при выборе xmin 0,47 или xmin 0,57 результат был бы только хуже.
Схема неудобна тем, что каждый раз приходится искать 2 новые точки и 2 новых значения функции. Оказывается, если делить отрезок не на равные части, а в отношении 0,382 : 0,236 : 0,382, то при удалении участка [c, d] бывшая точка b на следующем шаге всегда будет становиться точкой c.
Наоборот, бывшая точка c станет точкой b, если удалить участок [a, b]. Тогда достаточно найти точку на расстоянии 0,382(d–a) от a или от d соответственно и найти значение функции в этой точке, а потом сравнить со значением, уже известным из предыдущего шага.
Указанное свойство объясняется тем, что точка b делит отрезок [a, c] в той же пропорции, что точка c – отрезок [a, d], а именно в отношении 0,5 5 1 0,618 . Такая пропорция называется "золотым сечением". Таким образом можно примерно в 2 раза ускорить вычисления, хотя число шагов почти не уменьшается. Уменьшается же число действий на каждом шаге. Для достижения точности
необходимо log |
|
d a |
приближений, где d a – длина начального отрезка. |
|
1,618 |
|
|||
|
|
|||
|
|
|
Общая схема метода золотого сечения
Даны отрезок [a, d] и f x . По-прежнему ищем точку глобального минимума xmin с точностью .
50
1) Найдём b a 0,382 d a и c a 0,618 d a ; |
|
2) если c b , то xmin b при f b f c и xmin c при |
f b f c , и вычис- |
ления прекращаем; если же c b , переходим к п.3; |
|
3) если f b f c , то a a, d c, c b, b a d c a=a, |
d=c, c=b, b=a+d–c. |
Иначе (если f b f c ) находим a b, b c, d d, c d a b ;
4)переходим к п.2.
Всхеме в п.3 при пересчёте b и c учитываются новые значения других точек. Формулы b a 0,382 d a и b a d c равносильны, поскольку b и c от-
стоят на одинаковом расстоянии от a и от d соответственно. Также равносильны формулы c a 0,618 d a и c d b a , то есть c d a b .
Пример. Найдём точку глобального минимума функции f x x 2 3x 3 на отрезке [0, 2] с точностью 0,1. Вычисления проведём с двумя запасными цифрами для наглядности.
Решение. Шаг 1. Длина отрезка [0, 2] равна 2. Делим его на три части точка-
ми a 0 , b 2 0,382 0,764 , c 2 0,618 1,236 , d 2 . Находим
f 0,764 0,7642 3 0,764 3 1,292 и |
f 1,236 1,2362 |
31,236 3 0,820 . |
Поскольку f 0,764 f 1,236 , оставляем |
участок 0,764; |
2 в качестве нового |
отрезка. |
|
|
Шаг 2. Отрезок 0,764; 2 делится на три части точками
a 0,764, b 1,236, d 2, c 2 0,764 1,236 1,528 .
Считаем f 0,764 1,292 (уже известно) и f 1,528 1,5282 31,528 3 0,751.
Поскольку f 1,236 f 1,528 , оставляем участок 1,236; 2 в качестве нового отрезка.
Шаг 3. Отрезок 1,236; 2 делится на три части точками
a 1,236, b 1,528, c 2 1,236 1,528 1,708, d 2 .
Сравним f 1,528 0,751 |
(известно) и f 1,708 1,7082 31,708 3 0,793 . |
Поскольку f 1,528 f 1,708 , оставляем 1,236; 1,708 .
Шаг 4. Отрезок 1,236; 1,708 делится на три части точками
a 1,236, b 1,236 1,708 1,528 1,416, c 1,528, d 1,708
Вычислим f 1,416 1,4162 31,416 3 0,757 и учтём, что f(1,528) = 0,751.
Поскольку f 1,416 f 1,528 , оставляем 1,416; 1,708 для следующего шага. Шаг 5. Отрезок 1,416; 1,708 делим точками
51
a 1,416, b 1,528, c 1,708 1,416 1,528 1,596, d 1,708.
Замечаем, что |
c b 1,596 1,528 0,068 0,1, |
поэтому осталось сравнить |
f 1,528 0,751 |
и f 1,596 . Находим f 1,596 1,5962 |
31,596 3 0,759 . |
Поскольку |
f 1,528 f 1,596 , в качестве точки глобального минимума указы- |
ваем xmin 1,528, округлив до 1,5. Ответ: xmin 1,5 с точностью 0,1.
Указывать в ответе 1,528 или 1,53 нет смысла, поскольку цифры после 5 неверные. Точное решение примера – также 1,5. Совпадение приближённого решения с настоящим при низкой точности вычислений случайно и объясняется отсутствием цифр после 5 в точном решении.
Замечание. При замене функции на f x x 2 3,008x 3 и решении его с точностью 0,1 или 0,01 мы бы получили (после округления) то же решение xmin 1,5, но погрешность по сравнению с точным решением 1,554 составила бы 0,004 .
§3. Численное интегрирование
3.1.Основные трудности точного интегрирования
Для функций f x , непрерывных на отрезке a; b , существует определённый интеграл ab f x dx . Если известна первообразная функция F(x), для которой во
всех точках x a;b выполнено условие |
F x f x , то интеграл можно найти |
по формуле Ньютона – Лейбница |
|
b
f x dx F b F a .
a
Трудность в том, что общего способа поиска первообразной не существует. При поиске первообразной небольшое изменение функции может полностью изменить как результат, так и способ его получения.
Кроме того, первообразные многих функций вообще нельзя указать аналитически в виде элементарных функций. Хорошо известны интегралы
sin x2 dx, |
|
dx |
, |
e x2 dx, |
|
ex |
dx |
|
ln x |
x |
|||||||
|
|
|
|
|
|
|||
|
|
52 |
|
|
|
|