Итерационное уточнение корней

Поможем в ✍️ написании учебной работы

Имя

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

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

СОДЕРЖАНИЕ

1. Численное решение нелинейных уравнений……….………………. 1.1.Локализация корней…..………………………………………….. 1.2. Итерационное уточнение корней………………………………... 1.2.1. Метод бисекции…………………………………………………... 1.2.2. Метод простой итерации……….………………………………… 1.2.3. Метод Ньютона-Рафсона………………………………………… 1.3. Критерий окончания итерационного процесса…………............. 1.4. Преобразование уравнения к итерационному виду……............. 2. Вычисление алгебраического полинома………………...………….. 2.1. Схема Горнера…………………………………………….............. 2.2. Метод Ньютона-Рафсона………………………………………… 2.3. Метод Бирге-Виета……………………………………………….. 3. Решение СЛАУ……………………………………………………….. 3.1. Метод Гаусса……………………………………………………… 3.2. Метод Гаусса-Зейделя……………………………………............. 4 Нормы векторов и матриц…………………………………….............. 4.1. Норма вектора…………………………………………………….. 4.2. Абсолютная и относительная погрешности вектора…………… 4.3. Норма матрицы…………………………………………………… 5. Обусловленность вычислительной задачи………………………….. 5.1. Число обусловленности………………………………………….. 5.2. Обусловленность задачи вычисления определенного интеграла………………………………………............. 5.3. Обусловленность задачи решения СЛАУ………………............. 6. Методы интерполяции……………………………………………….. 6.1. Интерполяция обобщёнными многочленами…………………... 6.2. Кусочно-полиномиальная интерполяция……………………….. 6.3. Оценка погрешности полиномиальной интерполяции………… 6.4. Интерполяция сплайнами………………………………………... 6.5. Интерполяционная формула Лагранжа для равноотстоящих узлов…………………………………………………... 7. Вычисление определённых интегралов ……………………………... 7.1. Формула трапеции………………………………………………... 7.2. Формула Симпсона……………………………………………….. 7.3. Формула Симпсона 3/8…………………………………………… 7.4. Формула Буля……………………………………………………... 8. Решение СНАУ……………………………………………………….. 8.1. Метод покоординатного спуска………………………………….. 8.1.1 Задача нелинейного программирования ………………………… 8.1.2 Необходимые и достаточные условия оптимальности ………… 8.1.3 Задача безусловной оптимизации ………………………………... 8.1.4 Содержательная интерпретация…………………………………... 8.1.5 Структура МНК…………………………………………………… 8.1.6 Численные методы безусловной оптимизации…………………. 8.1.7 Прямые методы безусловной оптимизации. Циклический покоординатный спуск ………………………………………………… 8.1.8 Методы параболической интерполяции ………………………… 9. Численное решение дифференциальных уравнений……………….. 9.1. Задача Коши для обыкновенного дифференциального уравнения…………………………………………………………………. 9.1.1 Метод Эйлера ……………………………………………………… 9.1.2 Модифицированный метод Эйлера ……………………………… 9.1.3 Метод Рунге-Кутты ……………………………………………… 9.2. Решение задачи Коши для системы обыкновенных дифференциальных уравнений…………………………………………. 9.3. Решение задачи Коши для ОДУ второго и более высокого порядков………………………………………………………………….. 9.4. Осциллятор Ван дер Поля………………………………………….. Список литературы………………………………………………………

4 5 12 12 15 22 25 27 30 30 32 34 37 37 47 52 52 55 55 61 63 63 65 70 71 73 75 76 83 87 89 90 91 93 95 96 97 98 98 100 101 104 105 106 115 115 116 118 118 121 123 129 131

1. Численное решение нелинейных уравнений

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

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

(1)

- конечный или бесконечный интервал; (2)
- область определения функции ;
непрерывна на .

Так как подавляющее большинство нелинейных уравнений вида (1) не решается аналитическими (точными) методами, то на практике применяют численные методы.

Решить уравнение (1) означает, что надо:

1. Установить, имеет ли оно корни.

2. Определить, сколько корней.

3. Найти значения корней с заданной точностью.

Таким образом, решение задачи (1) состоит из следующих этапов:

1 этап: локализация корней, т.е. нахождение достаточно малых отрезков из области определения таких, что

в которых содержится одно значение корня:

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

Локализация корней

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

1. – они не пересекаются между собой;

2. – они содержат в себе корень исходного уравнения

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

Если график построить затруднительно, то уравнение (1) следует попытаться представить в эквивалентном виде:

(3)

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

Задача 1.1.

Осуществить локализацию корней следующего уравнения:

Решение. Введём две функции:

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

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

Ответ:

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

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

Замечание. Для корня чётной кратности это положение не выполняется, т.к. в малой окрестности такого корня функция имеет постоянный знак.

2. Второе положение – следствие из первого. Если строго монотонна отрезке , а также если (разные знаки на концах отрезка), то – единственный корень уравнения на данном отрезке.

Задача 1.2.

Локализовать корни уравнения .

Решение. Вначале упростим себе жизнь и разделим обе части уравнения на 4, затем, как и в предыдущем примере, разделимся на 2 функции:

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

Ответ:

Осуществим проверку на смену знака исходной функции на каждом из интервалов:

Значит, на каждом из отрезков находится хотя бы один корень.

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

Задача 1.3.

Локализовать корни уравнения на интервале .

Решение. Локализуем корни данного уравнения первым способом.

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

Видно, что функция меняет знак в трёх местах:

Значит, корней всего три и мы их локализовали. Ответ:

Метод бисекции

Также называется метод деления отрезка пополам. Это простейший и достаточно надёжный метод итерационного уточнения корней.

Пусть – отрезок, являющийся результатом локализации, при этом функция на нём непрерывна и – единственный корень на данном интервале.

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

Шаг 1: Задаём – точность вычисления результата. Покажем , , ,

Шаг 2: Если , то , иначе переход к шагу 3.

Шаг 3: Если , то , иначе переход к шагу 4.

Шаг 4: Если , то полагаем и переход к шагу 6, иначе переход к шагу 5.

Шаг 5: Полагаем

Шаг 6: Полагаем

Шаг 7: , переход к шагу 2.

Примечания :

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

2. Этот алгоритм неприменим для нахождения корня кратной чётности, т.к. .

3. Замечание относительно погрешности. Если корень , то погрешность приближения не превышает половины длины отрезка :

Задача 1.4.

Рассмотрим уравнение

Найти методом бисекции с точностью положительный корень уравнения .

В предыдущем примере этот корень был локализован на .

Примем .

Положим ; ; .

Результаты нескольких итераций приведены в таблице:

Ит.	Значения	Точность	Что дальше
0			Знак меняется в правой части, убираем левую
1			Знак меняется в левой части, убираем правую
2			Убираем левую часть
3			Убираем левую часть
4			Убираем правую часть
5			Убираем левую часть
6			Достигнута заданная точность

Ответ: при имеем . Заданная точность достигнута. Можно принять .

1.2.2. Метод простой итерации

Преобразуем исходное уравнение к следующему эквивалентному виду:

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

Получаем новое приближение . Снова подставляем его в правую часть:

и т.д.

Таким образом, мы организуем следующий итерационный процесс

Если - непрерывная функция, а последовательность сходится, то существует предел, являющийся решением этого уравнения:

Обоснование.

Пусть выражение верно.

Тогда перейдём к пределу в равенстве, описывающем итерационный процесс. Получаем:

Так как , то и .

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

Достаточное условие сходимости итерационного процесса (4) формулируется в виде следующей теоремы:

Теорема.

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

1. Функция определена и дифференцируема на этом интервале;

2. ;

3. Её производная такова, что .

Тогда последовательность сходится монотонно при любом начальном приближении .

Вот геометрическая интерпретация достаточного условия сходимости.

Случай А. Производная функции положительна на отрезке и везде по модулю меньше единицы ( ). Это означает, что угол наклона касательной в каждой точке исходной функции меньше 45° ( ), то есть наша функция монотонно возрастает, является вогнутой и в пределах нужного нам отрезка находится ниже прямой (угол наклона которой и составляет 45°).

Случай Б. Производная функции отрицательна на отрезке и везде по модулю меньше единицы ( ). Это означает что угол наклона касательной в каждой точке исходной функции больше 45° ( ), то есть наша функция монотонно убывает и является вогнутой и угол наклона её касательных изменяется от 0° до 45°.

Тогда последовательность сходится колебательно.

Случай В. Производная функции положительна на отрезке и в некоторых местах становится больше единицы ( ). Это означает, что в функции найдутся места, в которых угол наклона касательной больше 45°.

Тогда последовательность расходится, потому что не выполняется достаточное условие. Причём расходимость монотонная.

Случай Г. Производная функции отрицательна на отрезке и в некоторых местах становится больше единицы ( ). Это означает что в функции найдутся места, в которых угол наклона касательной меньше 45°.

Тогда последовательность расходится, потому что не выполняется достаточное условие. Причём расходимость колебательная.

Оценка погрешности.

Критерий окончания итерационного процесса определяется на основе априорной оценки процесса.

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

Где - максимальная скорость роста производной.

Из этой формулы следует, что вычисления стоит вести до выполнения следующего условия:

Процесс должен быть остановлен после достижения заданной точности.

Задача 1.5.

Решить уравнение методом простой итерации с точностью . Найти корень на интервале .

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

Проверим достаточное условие сходимости:

1. Производная на отрезке существует.

2. - скорость роста функции по модулю меньше 1.

Вычислим критерий останова:

Пусть начальным приближением будет середина заданного отрезка . Тогда мы можем начать итерационный процесс:




	- условие останова выполнено

Ответ:

Метод Ньютона-Рафсона

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

Тогда разложим функцию в ряд Тейлора (т.е. осуществим линеаризацию):

Причём точность приближения увеличивается при .

Дальше вместо исходного уравнения мы будем решать это приближённое уравнение:

Разрешив его относительно , получим:

Основная формула метода Ньютона-Рафсона имеет вид:

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

Формула Ньютона-Рафсона и сам метод имеет следующую геометрическую интерпретацию:

1. В точке график заменяется на касательную.

2. Точка пересечения касательной с осью принимается за новое приближение .

3. Далее строится точка , в которой снова строится касательная.

4. И так далее до тех пор, пока не будет достигнута заданная точность.

Обоснование.

Будем обозначать отрезок как .

Тогда тангенс угла наклона, или производная в точке касания будет равна , значит . С учётом формулы Ньютона-Рафсона: .

Примечание 1.

Формулу Ньютона-Рафсона можно интерпретировать следующим образом.

Предположим, что . Тогда перейдём от уравнения к равносильному уравнению , и на основании формулы Ньютона-Рафсона это будет означать, что:

Применительно к уравнению вида метод Ньютона-Рафсона реализует схему метода простых итераций. При этом:

Тогда по определению следует, что

Примечание 2.

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

Примечание 3.

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

Схема Горнера

Рассмотрим этот метод на примере полинома пятого порядка:

Предположим, что - корень этого многочлена. Разделим на . Тогда исходный полином можно представить в виде:

где между коэффициентами a и b есть связь. Вычислим её. Раскрыв скобки, и сгруппировав известные и неизвестные величины, получим:

Теперь приравняем соответствующие коэффициенты a и b между собой:

Разрешим эту систему относительно коэффициентов b:

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

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

А правило Горнера в общем виде записывается так:

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

Метод Бирге-Виета

Метод Бирге-Виета представляет из себя улучшенный метод Ньютона-Рафсона с помощью схемы Горнера.

Пусть у нас есть уравнение , где - полином n порядка, и итерационная формула Ньютона-Рафсона .

По правилу Горнера можно получить - смотри формулу (*).

И по формуле (*) .

Тогда - отсюда получается, что .

Но: - многочлен степени, поэтому его также можно вычислить по схеме Горнера в следующем виде:

И подставляя найденные и в формулу Ньютона-Рафсона получаем:

Это и есть основная формула метода Бирге-Виета.

Задача 3.1.

Найти корень полинома , расположенный вблизи значения .

Решение методом Ньютона-Рафсона:

Ответ:

Решение схемой Горнера:

- для нахождения

Первая итерация :

Вторая итерация :

Третья итерация :

Обратите внимание, что дальше считать не имеет смысла - с точностью до 4 знаков – заданная точность достигнута.

Ответ:

Решение СЛАУ

СЛАУ – Система Линейных Алгебраических Уравнений – это уравнение вида:

где – матрица размерностью , и – вектор-столбцы , при этом матрица не вырожденная (её определитель не равен нулю).

(1)

Методы решения СЛАУ бывают прямые и итерационные.

Метод Гаусса

Метод Гаусса – это прямой метод решения СЛАУ. Это метод последовательного исключения неизвестных. Относится к простым методам, т.е. позволяет получить решение СЛАУ за конечное число шагов. Если все операции выполняются точно (без ошибок округления), то решение СЛАУ также получается точным. Метод Гаусса (как и другие простые методы: Крамера, метод ортогонализации и другие) применяется на практике для решения СЛАУ на ЭВМ, как правило, с числами порядка .

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

Верхняя треугольная матрица – это матрица, в которой все элементы ниже главной диагонали равны нулю.

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

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

Существуют три элементарные операции над расширенной матрицей, которые приведут к решению эквивалентной СЛАУ:

1. Перестановка – любые две строки можно поменять местами;

2. Масштабирование – любую строку можно умножить на константу, не равную нулю;

3. Замещение – любую строку можно заменить суммой этой же строки и любой другой строки, умноженную на константу, не равную нулю.

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

Алгоритм метода Гаусса.

Запишем расширенную матрицу

(2)

ШАГ 1.

Полагаем .

ШАГ 2.

Находим максимальный по модулю элемент среди элементов -го столбца, расположенных не выше главной диагонали:

(3)

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

(4)

ШАГ 3.

Полагаем .

ШАГ 4.

Вычисляем коэффициент

(5)

ШАГ 5.

Положим

(6)

ШАГ 6.

Полагаем . Если , то переходим к шагу 4, иначе переходим к шагу 7.

ШАГ 7.

Полагаем . Если , то переходим к шагу 2, иначе переходим к шагу 8.

ШАГ 8.

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

(7)

ШАГ 9.

Начинаем процесс обратной подстановки:

(8)

ШАГ 10.

Stop.

Замечание. Существует стратегия тривиального выбора главного элемента : если , то строки не переставляются, и – главный элемент. Если , то ищем первую строку ниже , где элемент и меняем эти строки местами.

Пример 1. Решить СЛАУ:

Применим для простоты стратегию тривиального выбора.

Расширенная матрица:

Обратный ход:

Пример 2. Иллюстрирует, как использование стратегии тривиального выбора главного элемента в методе исключения Гаусса может привести к значительной ошибке в решении СЛАУ.

Существует точное решение СЛАУ:

I. Будем использовать арифметику с четырьмя знаками точности, плюс стратегию тривиального выбора.

Ошибка обусловлена большим коэффициентом .

II. Применим стратегию выбора наибольшего главного элемента.
Т.к. , меняем местами строки. Получаем:

Замечание: Известно, что чем меньше коэффициенты , тем меньше относительная ошибка при выполнении операций +, –, *, /, тем точнее СЛАУ.

Решение.

Прямой ход.

Шаг 1. ;

Расширенная матрица преобразуется к виду:

Шаг 2.

Расширенная матрица преобразуется к виду:

Действительно,

Однако, для шестиразрядной сетки будет получено .

Обратный ход.

Для шестиразрядной сетки получим

Таким образом:

– плохо!

Пример 2*.

Решить систему (*) методом Гаусса с выбором главного элемента по столбцу на шестиразрядной десятичной ЭВМ.

Получаем:

– решение получилось точным.

Решение.

Прямой ход.

Шаг 1. В первом столбце максимальный элемент находится на диагонали, поэтому перестановка уравнений не требуется, и шаг 1 осуществляется так же, как и в предыдущем примере.

Шаг 2. Во втором столбце

поэтому необходимо поменять местами второе и третье уравнения. Получаем:

Тогда

Метод Гаусса-Зейделя

Метод Гаусса-Зейделя является итерационным методом.

Рассмотрим самое обычное СЛАУ:

(1)

Выполним следующие преобразования.

Умножим обе части уравнения на транспонированную матрицу слева (напомним, что умножение матриц некоммутативно!):

(2)

Введём следующие обозначения:

После этого будем заниматься решением следующей СЛАУ, которая эквивалентна исходной:

(3)

Такая СЛАУ называется нормальной, так как матрица C в данном случае будет симметрична относительно главной диагонали. Это свойство нормальности позволяет привести СЛАУ к следующему виду:

(4)

где (5)

и (6)

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

Обозначим начальное приближение для решения СЛАУ вида .

Вычислим новое приближение по следующим формулам в соответствии с вышеописанной теоретической базой:

(7.1)

(7.2)

(7.3)

Обратите внимание, что в формировании первого соотношения участвует только первое уравнение, в формировании второго – два первых уравнения и так далее. Поэтому этот метод является достаточно экономичным. Соотношение в общем виде выглядит так:

(7.i)

А последнее вычисление имеет вид:

(7.n)

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

Существуют два критерия останова итерационного процесса метода Гаусса-Зейделя – максимальное количество итераций и заданная точность .

Справедливо также то, что итерационный процесс Гаусса-Зейделя для приведённой СЛАУ, эквивалентной нормальной, всегда сходится к единственному решению этой системы при любом выборе .

Теперь в полной мере запишем алгоритм:

ШАГ 1.

Задать – точность вычислений.

ШАГ 2.

Вычислить ; ; нормальной системы (3).

ШАГ 3.

Приведение (3) к виду (4)-(6).

ШАГ 4.

Осуществления итерационного процесса по формулам (7).

ШАГ 5.

Вычисление

ШАГ 6.

Если ,
то , Stop
иначе переход к шагу 4.

Задача 4.2.

Решение.

Теперь приведём СЛАУ к нормальному виду:

Расставляем индексы:

Возьмём начальное приближение :

Ответ:

Нормы векторов и матриц

Рассмотрим СЛАУ в матричном виде

(1)

где ; ; .

Пусть – точное решение (1),

– приблизительное решение (1): .

Погрешность: .

, , , т.е. являются элементами векторного пространства.

Для оценки величин векторов , , используется понятие нормы вектора.

Норма вектора

Говорят, что в пространстве задана норма, если каждому сопоставлено число (читается – «норма икс»), обладающее свойствами:

1. всегда,

тогда и только тогда, когда

Наиболее распространена норма следующего вида:

(2)

Но на практике чаще всего используются следующие частные случаи:

1. (3)

2. (4)

3. (5)

Примечания:

1. Норма - обычная евклидова норма.

2. Формула для получена из формулы для с помощью предельного перехода при .

3. Верно следующее неравенство:

Доказательство:
,

В то же время:

Приведём пример. Дан вектор .
Найти: , , .

Проверим отношения норм:

Задача 6.1.

Дан вектор в трёхмерном пространстве .

Найти его нормы .

Решение.

Норма матрицы

Нормой матрицы называется величина:

Норма матрицы обладает следующими свойствами:

1. всегда,

тогда и только тогда, когда матрица A нулевая.

Верны также и следующие дополнительные свойства:

Наиболее часто используются следующие нормы:

- берётся максимальная из сумм модулей элементов столбцов,

, где - собственные числа матрицы ,

- берётся максимальная из сумм модулей элементов строк,

- Евклидова норма.

Для оценки нормы можно использовать неравенство .

Норма матрицы имеет следующую геометрическую интерпретацию:

Геометрически это означает, что в пространстве вектор поворачивается и вытягивается:

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

Задача 6.2. Дана матрица:

Найти:

Вычислим собственные значения матрицы :

– симметричная матрица, следовательно она имеет вещественные собственные значения.

Определение. Число называется собственным числом матрицы , если .

Определим

Вычислим .

Алгоритм нахождения обратной матрицы:

1) Находим определитель исходной матрицы. Если , то – невырожденная матрица и существует.

2) Находим .

3) Находим алгебраические дополнения элементов . Составляем из них присоединённую матрицу .

4) Вычисляем обратную матрицу по формуле:

5) Делаем проверку:

Число обусловленности

Если между абсолютными погрешностями установлено неравенство

(6)

то величину назовём абсолютным числом обусловленности.

А если установлено следующее неравенство между относительными погрешностями

(7)

То величину назовём относительным числом обусловленности.

Следует отметить, что в неравенствах (6), (7) с тем же успехом вместо и можно пользоваться и .

Выводы.

1. Если знакопостоянна на , то , и задача вычисления определённого интеграла хорошо обусловлена.

2. Если на принимает значения разных знаков, то .

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

Задача 7.1.

Рассмотрим СЛАУ:

(7)

Решение этой СЛАУ с точностью до трёх знаков:

Предположим, что вектор правых частей

получен не точно, а с погрешностью. Пусть он определён с точностью до . Сделаем возмущения:

Решением системы, соответствующим , является

Вычислим относительную погрешность задания правой части:

Относительная погрешность решения, соответствующая :

Таким образом погрешность возросла в

раз.

Вычислим стандартное число обусловленности:

Геометрическая интерпретация:

Первому уравнению в (7) соответствует прямая:

Второму уравнению в (7) соответствует прямая:

Методы интерполяции

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

Пусть функция задана таблицей n значений:

То есть .

Точки называются интерполяционными узлами.

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

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

Классическая постановка задачи интерполяции состоит в построении такой функции , что .

Задача 8.1.

Функция задана следующей таблицей:

Построить многочлен Лагранжа и найти .

Решение. , значит многочлен Лагранжа имеет вторую степень:

Многочлен Лагранжа:

Значение :

Задача 8.2.

	0	1	2	3	4
	1.0	1.8	2.2	1.4	1.0

Разобьём отрезок на части и , и построим многочлены Лагранжа соответственно и .

В результате вычислений получается:

Главное условие кусочно-полиномиальной интерполяции выполняется.

Но, с другой стороны, если посчитать производные, то мы увидим основной недостаток данного метода:

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

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

Интерполяция сплайнами

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

Пусть задана таблицей:

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

1. На всём отрезке имеет непрерывные производные до порядка включительно.

2. На каждом из частичных отрезков является многочленом степени .

3. для .

Дефект сплайна – это разность .

Самый распространённый вид сплайна – это кубический сплайн с дефектом 1. Рассмотрим его.

По определению сплайн на любом отрезке является многочленом порядка - :

Раз это – кубический многочлен, то мы будем искать по следующей формуле:

где коэффициенты неизвестны и именно их и надо найти – всего неизвестных.

По определению сплайна должны выполняться условия совпадения в узлах интерполяции:

Через мы обозначили шаг между текущим и предыдущим узлами интерполяции.

Итак, мы получили линейных алгебраических уравнений. Чтобы получить оставшиеся , потребуем непрерывности производных на отрезке . Так как мы составляем сплайн 3 порядка с дефектом 1, то необходимо выполнить непрерывность производных – первой и второй :

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

Считаем производные:

Приравнивая левые и правые соответствующие производные, получаем ещё линейных алгебраических уравнений:

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

Выдвигаемые требования могут быть разные. Достаточно вторую производную в этих точках приравнять к каким-либо числам и . Самое простое требование – это требование нулевой кривизны – положить эти числа равными нулю.

Теперь все уравнений выведены и давайте соберём их в одну СЛАУ:

Исключим из этой системы , так как они уже известны, и получим:

Эта система содержит все необходимые уравнения для получения . Можно доказать, что решение этой СЛАУ существует.

Задача 8.3.

Функция задана таблицей:

0	1	2	3	4
0	1	2	3	4
1.0	1.8	2.2	1.4	1.0

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

Решение.

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

Итого получилась СЛАУ из 11 уравнений с 11 неизвестными:

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

Искомый сплайн описывается следующим набором:

Задача 8.4.

Функция задана в виде таблицы:

0	1	2
2	3	4
4	-2	6

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

Решение.

Ответ:

Формула трапеции

При имеем .

Тогда из (7) для формулы Ньютона-Котса получаем коэффициенты и :

;

И по формуле Ньютона-Котса (8) на получаем:

(9)

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

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

Формула Симпсона

Как известно, через три точки можно провести параболу.

При и из (7) последовательно получим:

Тогда, с учётом (8), получаем:

(10)

Это – формула Симпсона. Геометрически это означает то, что интегрируемая функция заменяется не на прямую, как в формуле трапеции, а на параболу, что даёт немного более точный результат:

Формула Симпсона 3/8

При и последовательно получим:

В конечном итоге получим:

– формула Симпсона 3/8.

Геометрически это – кубическая парабола

Формула Буля

Задача.

Вычислить ОИ с помощью каждой из формул (кроме 3/8):

Рассчитать относительную погрешность каждого решения, если точное решение .

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

0	1	2	3	4
0	0.25	0.5	0.75	1
1	1.6553	1.5515	1.0666	0.7216

Формула трапеции.

Воспользуемся методом «разделяй и властвуй».


1	1.6553	0.3319
1.6553	1.5515	0.4009
1.5515	1.0666	0.3273
1.0666	0.7216	0.2235
Сумма:		1.2836

Формула Симпсона


1	1.6553	1.5515	0.7644
1.5515	1.0666	0.7216	0.5450
Сумма:			1.3094

Формула Буля


1	1.6553	1.5515	1.0666	0.7216	1.3086

Результат

Точно	Формула Трапеции	Формула Симпсона	Формула Буля
1.3083	1.2836	1.3094	1.3086
-	0.0247	0.0011	0.0003
-	0.0189	0.0008	0.0002

Решение СНАУ

Надо решить систему уравнений:

(1)

где , ,…, – заданные нелинейные функции. Среди них могут быть и линейные функции, но нелинейность хотя бы одной приводит к нелинейной системе уравнений. Поэтому система (1) называется нелинейной.

Систему (1) можно записать в векторном виде:

, (2)

где

, , ,

– вектор неизвестных, – нелинейная вектор-функция от вектора . Решением системы (2) называется вектор , при подстановке которого в систему (2) она превращается в тождество.

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

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

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

Стационарные точки.

Теорема 2 (достаточное условие).

Пусть:

1) – дважды непрерывно дифференцируема в по ;

2) – стационарная точка.

Для того чтобы была решением задачи (3), достаточно, чтобы матрица Гессе Н в точке была:

1) Положительно определенной ( );

2) Отрицательно определенной ( ).

Теорема (Критерий Сильвестра).

Для того чтобы симметричная матрица Н была положительно определенной, необходимо и достаточно, чтобы все главные миноры матрицы были положительны:

Для отрицательно определённых матриц знаки главных миноров чередуются, начиная со знака для :

Замечание. Если Н знакоопределенная, то все её главные миноры .

Структура МНК.

Этап 1. Устанавливается общий вид зависимости от :

Например,

и так далее.

Строится функция:

(5)

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

Этап 2.

Решается задача безусловной оптимизации:

(6)

– наилучшая кривая в смысле:

Задача:

Пусть

Тогда:

; (7)

Необходимые условия оптимальности:

Получили систему уравнений:

(8)

Матрица Гессе .

в задаче (7).

Задача 1.

Рассмотри систему нелинейных уравнений:

Найти методом покоординатного спуска корни данной системы, если начальное приближение ; .

Решение.

Для начала составим целевую функцию:

;

, – базисные векторы;

– начальное приближение;

1 ) Пусть ; .

;


0	0,5	1,0
150,0625	26,2909	64,1393

;

2) Пусть ; .

;


0	0,4	0,8
5,1192	0,9414	62,8702

;

– Не выполняется!

⟹

;

3) Пусть ; .

;


0	0,03	0,06
0,7925	0,076	0,2362

;

4) Пусть ; .

;


0	0,002	0,004
0,0276	0,0273	0,0275

;

– Не выполняется!

⟹

;

Метод Эйлера.

Метод Эйлера играет важную роль в теории численных методов решения ОДУ, хотя и не часто используется в практических расчетах из-за невысокой точности.

Численное решение задачи Коши состоит в построении таблицы приближенных значений в точках .
Точки называются узлами сетки, а величина h - шагом сетки.

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

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

Найдем величину локальной погрешности метода Эйлера: ,

при условии, что .

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

В качестве меры абсолютной погрешности метода примем величину .

Можно показать, что для явных одношаговых методов из того, что локальная погрешность имеет вид следует, что , где C и M - некоторые константы.

Таким образом, метод Эйлера является методом первого порядка точности. Для нахождения решения задачи Коши с заданной точностью требуется найти такое приближенное решение , для которого величина глобальной погрешности .

Так как точное решение задачи неизвестно, погрешность оценивают с помощью правила Рунге.

Правило Рунге оценки погрешностей. Для практической оценки погрешности проводят вычисления с шагами . За оценку погрешности решения, полученного с шагом , принимают величину, равную , где p - порядок метода.

Метод Рунге-Кутты.

Методом Рунге-Кутты четвертого порядка точности называют одношаговый метод, относящийся к широкому классу методов Рунге-Кутты. В этом методе величины вычисляются по следующим формулам:

Контроль точности на каждом шаге h.

Основным способом контроля точности получаемого численного решения при решении задачи Коши является методы, основанные на принципе Рунге-Ромберга-Ричардсона.

В случае метода Рунге-Кутты четвертого порядка точности следует на каждом шаге h рассчитывать параметр

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

Алгоритм метода Эйлера .

ШАГ 1. Задать отрезок [a;b]; задать число шагов ; задать начальное условие

ШАГ 2. Высчитать шаг

ШАГ 3. Если , то переходим к шагу 4, иначе к шагу 5.

ШАГ 4. ; ;

ШАГ 5. Stop.

Алгоритм модифицированного метода Эйлера .

ШАГ 1. Задать отрезок [a;b]; задать число шагов ; задать начальное условие

ШАГ 2. Высчитать шаг

ШАГ 3. Если , то переходим к шагу 4, иначе к шагу 5.

ШАГ 4. ; ; ;

ШАГ 5. Stop.

Алгоритм Рунге-Кутты .

ШАГ 1. Задать отрезок [a;b]; задать число шагов ; задать начальное условие

ШАГ 2. Высчитать шаг

ШАГ 3. Если , то переходим к шагу 4, иначе к шагу 5.

ШАГ 4. ;

;

ШАГ 5. Stop.

Список литературы

Основная литература

1. Амосов А.А., Дубинский Ю.Д., Копчёнова Н.В. «Вычислительные методы для инженеров» – М.: Высшая шк., 1994 – 544 с.

2. Рябенький А.С. «Введение в дискретную математику: Учебное пособие для вузов» – М.: Физматлит, 1994 – 336 с.

3. Азаров А.И., Басик В.А. и др. «Сборник задач по методам вычислений: учебное пособие для вузов» - под ред. Монастырского – М.: Физматлит, 1991 – 320 с.

4. Дж. Мэтьюз, К. Финг, «Численные методы. Использование MATLAB» / пер. с англ – М.: Вильямс, 2001 – 720 с.

5. «Начало работы в MATLAB» / пер. с англ Конюшенко В.В. – http://www.exponenta.ru/educat/free/matlab/gs.pdf

Дополнительная литература

6. Бахвалов Н.С. «Численные методы, ч.1» – М.: Наука, 1975 – 631 с.

7. Дж. Фарсайт, М. Малькольм «Машинные методы математических вычислений» – М.: Мир, 1980 – 279 с.

СОДЕРЖАНИЕ

4 5 12 12 15 22 25 27 30 30 32 34 37 37 47 52 52 55 55 61 63 63 65 70 71 73 75 76 83 87 89 90 91 93 95 96 97 98 98 100 101 104 105 106 115 115 116 118 118 121 123 129 131

1. Численное решение нелинейных уравнений

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

(1)

- конечный или бесконечный интервал; (2)
- область определения функции ;
непрерывна на .

Решить уравнение (1) означает, что надо:

1. Установить, имеет ли оно корни.

2. Определить, сколько корней.

3. Найти значения корней с заданной точностью.

Таким образом, решение задачи (1) состоит из следующих этапов:

1 этап: локализация корней, т.е. нахождение достаточно малых отрезков из области определения таких, что

в которых содержится одно значение корня:

Локализация корней

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

1. – они не пересекаются между собой;

2. – они содержат в себе корень исходного уравнения

Если график построить затруднительно, то уравнение (1) следует попытаться представить в эквивалентном виде:

(3)

Задача 1.1.

Осуществить локализацию корней следующего уравнения:

Решение. Введём две функции:

Ответ:

Задача 1.2.

Локализовать корни уравнения .

Ответ:

Осуществим проверку на смену знака исходной функции на каждом из интервалов:

Значит, на каждом из отрезков находится хотя бы один корень.

Задача 1.3.

Локализовать корни уравнения на интервале .

Решение. Локализуем корни данного уравнения первым способом.

Видно, что функция меняет знак в трёх местах:

Значит, корней всего три и мы их локализовали. Ответ:

Итерационное уточнение корней

Перейдём ко второму этапу решения поставленной задачи.

Итерационное уточнение корней – это вычислительный метод уточнения корня с заданной точностью.

Рассмотрим некоторые из этих методов.

Метод бисекции

Шаг 1: Задаём – точность вычисления результата. Покажем , , ,

Шаг 2: Если , то , иначе переход к шагу 3.

Шаг 3: Если , то , иначе переход к шагу 4.

Шаг 4: Если , то полагаем и переход к шагу 6, иначе переход к шагу 5.

Шаг 5: Полагаем

Шаг 6: Полагаем

Шаг 7: , переход к шагу 2.

Примечания :

2. Этот алгоритм неприменим для нахождения корня кратной чётности, т.к. .

Задача 1.4.

Рассмотрим уравнение

Найти методом бисекции с точностью положительный корень уравнения .

В предыдущем примере этот корень был локализован на .

Примем .

Положим ; ; .

Результаты нескольких итераций приведены в таблице:

Ит.	Значения	Точность	Что дальше
0			Знак меняется в правой части, убираем левую
1			Знак меняется в левой части, убираем правую
2			Убираем левую часть
3			Убираем левую часть
4			Убираем правую часть
5			Убираем левую часть
6			Достигнута заданная точность

Ответ: при имеем . Заданная точность достигнута. Можно принять .

1.2.2. Метод простой итерации

Преобразуем исходное уравнение к следующему эквивалентному виду:

Получаем новое приближение . Снова подставляем его в правую часть:

и т.д.

Таким образом, мы организуем следующий итерационный процесс

Обоснование.

Пусть выражение верно.

Тогда перейдём к пределу в равенстве, описывающем итерационный процесс. Получаем:

Так как , то и .

Достаточное условие сходимости итерационного процесса (4) формулируется в виде следующей теоремы:

Теорема.

1. Функция определена и дифференцируема на этом интервале;

2. ;

3. Её производная такова, что .

Тогда последовательность сходится монотонно при любом начальном приближении .

Вот геометрическая интерпретация достаточного условия сходимости.

Тогда последовательность сходится колебательно.

Оценка погрешности.

Критерий окончания итерационного процесса определяется на основе априорной оценки процесса.

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

Где - максимальная скорость роста производной.

Из этой формулы следует, что вычисления стоит вести до выполнения следующего условия:

Процесс должен быть остановлен после достижения заданной точности.

Задача 1.5.

Решить уравнение методом простой итерации с точностью . Найти корень на интервале .

Проверим достаточное условие сходимости:

1. Производная на отрезке существует.

2. - скорость роста функции по модулю меньше 1.

Вычислим критерий останова:

Пусть начальным приближением будет середина заданного отрезка . Тогда мы можем начать итерационный процесс:




	- условие останова выполнено

Ответ:

Метод Ньютона-Рафсона

Тогда разложим функцию в ряд Тейлора (т.е. осуществим линеаризацию):

Причём точность приближения увеличивается при .

Дальше вместо исходного уравнения мы будем решать это приближённое уравнение:

Разрешив его относительно , получим:

Основная формула метода Ньютона-Рафсона имеет вид:

Формула Ньютона-Рафсона и сам метод имеет следующую геометрическую интерпретацию:

1. В точке график заменяется на касательную.

2. Точка пересечения касательной с осью принимается за новое приближение .

3. Далее строится точка , в которой снова строится касательная.

4. И так далее до тех пор, пока не будет достигнута заданная точность.

Обоснование.

Будем обозначать отрезок как .

Примечание 1.

Формулу Ньютона-Рафсона можно интерпретировать следующим образом.

Применительно к уравнению вида метод Ньютона-Рафсона реализует схему метода простых итераций. При этом:

Тогда по определению следует, что

Примечание 2.

Примечание 3.

Дата: 2019-05-28, просмотров: 367.

12 3 4 5 6 7 8 9 10 Следующая ⇒