Вычислительные методы алгебры (лекции)
§1. Учет погрешностей вычислений.
При решении математических задач могут возникнуть погрешности по различным причинам:
При составлении математической модели физического процесса или явления приходится принимать условия, упрощающие постановку задачи. Поэтому математическая модель не отражает реальный процесс, а дает его идеализированную картину. Погрешность, возникающая при этом, называется погрешностью постановки задачи.
Часто приходится для решения задачи применять приближенный метод (интеграл заменяют квадратурной суммой, производную заменяют разностью, функцию – многочленом). Погрешность, возникающая при этом, называется погрешностью метода.
Часто исходные данные заданы не точно, а приближенно. При выполнении вычислений погрешность исходных данных в некоторой степени переходит в погрешность результата. Такая погрешность называется погрешностью действий.
Погрешность, возникающая при округлении бесконечных и конечных десятичных чисел, имеющих большее число десятичных знаков, чем надо в округлении, называется погрешностью округления.
Определение.
Пусть х – некоторое
число, число
а называется
его приближенным
значением,
если а в определенном
смысле мало
отличается
от х и заменяет
х в вычислениях,
.
Определение.
Погрешностью
приближенного
значения а
числа х
называется
разность
,
а модуль этой
погрешностью
называется
абсолютной
погрешностью.
Если
,
то а взято с
недостатком.
Если
,
то а взято с
избытком.
Определение.
Границей
погрешности
приближенного
значения а
числа х называется
всякое неотрицательное
число
,
которое не
меньше модуля
погрешности:
.
Говорят, что
приближение
а приближает
число х с точностью
до
,
если
,
,
.
Пример. Пусть а=0,273 – приближенное значение х с точность до 0,001. Указать границы, в которых заключается х.

При округлении чисел считают, что границы погрешности округления равна половине единицы округляемого разряда:
,
α – порядок
округления
разряда.
Определение. Относительной погрешностью приближенного значения а числа х называется отношение
.
Пример. Округлить до десятых число 27,52 и найти погрешность и относительную погрешность округления:
,
,
.
Также как и абсолютная погрешность относительная погрешность не всегда может быть вычислена и приходится оценивать ее модуль. Модуль относительной погрешности выражается в процентах. Чем меньше модуль относительной погрешности, тем выше качество приближения.
Определение.
Границей
относительной
погрешности
приближенного
значения а
числа х
называется
всякое неотрицательное
число
,
которое не
меньше модуля
относительной
погрешности:
.
Установим связь между границами погрешностей абсолютной и относительной:
- граница
относительной
погрешности;
- граница
абсолютной
погрешности.
.
§10. Вспомогательные сведения из функционального анализа.
Определение.
Множество Х
произвольных
элементов
называется
метрическим
пространством,
если
ставится в
соответствие
число
,
удовлетворяющее
следующим
условиям:
;
;
– расстояние
между x
и y.
1-3 – аксиомы метрики.
Говорят, что
множество
элементов
- метрическое
пространство
сходится
к
,
если

,
.
Последовательность
точек
называется
сходящейся
в себе (фундаментальной),
если
.
Всякая сходящаяся последовательность является фундаментальной, обратное верно не всегда.
Определение. Метрическое пространство, в котором всякая фундаментальная последовательность сходится называется полным.
Пример.
.
Зададим различными способами расстояния:
кубическая метрика, m-метрика
;
сферическая метрика,
метрика
;
октаэдрическая, s-метрика
.
Для всех
выполняются
аксиомы метрики
и в каждой
– полное метрическое
пространство.
Пусть X,Y – метрические пространства.
называется
оператором,
заданным в X
со значением
в Y.
Если X=Y,
то
– оператор,
отображающий
Х в себя (преобразование).
Если
,
то
– неподвижная
точка при отображении
.
Определение.
Говорят,
что отображение
называется
сжимающим
(сжатием),
если
.
§11. Решение уравнений с одним неизвестным. Дихотомия.
Пусть требуется
решить уравнение
(1),
где
– непрерывная
функция.
Число
называется
корнем
уравнения
(1), если
.
Если функция
определена
и непрерывна
на
и на концах
отрезка принимает
значения разных
знаков, то на
существует
хотя бы один
корень.
Отделить корень уравнения значит найти такой интервал, внутри которого находится один и только один корень данного уравнения.
Для отделения корней можно применить следующий признак:
Если на отрезке
функция
непрерывна
и монотонна,
и на концах
отрезка принимает
значения разных
знаков, то на
данном отрезке
существует
только один
корень уравнения
(1).
Достаточным условием монотонности функции на отрезке является сохранение знака производной.
Отделить корень можно и графически: нарисовать график и указать точки пересечения с осью Ох.
Совершенный метод отделения корней – метод Штурма.
Дихотомия (метод деления отрезка пополам).
Пусть

существует
хотя бы один
корень на
;
Рассмотрим
и
.
Из этих двух
выберем тот,
на концах которого
функция
принимает
значения разных
знаков и поделим
его пополам
и т.д.
Если нужно
найти корень
с точностью
до
,
то мы продолжаем
делить отрезок
до тех пор, пока
длина отрезка
не станет меньше
,
тогда середина
последнего
отрезка дает
значение корня
с требуемой
точностью.
Дихотомия проста и очень надежна: к простому корню она сходится всегда для любой непрерывной функции в том числе и недифференцируемой, при этом она устойчива к ошибкам округления. Скорость сходимости метода дихотомии не велика, т.е. за одну итерацию точность увеличивается вдвое.
Недостатки: прежде чем применить, необходимо найти отрезок, на концах которого функция принимает значения разных знаков. Если на этом отрезке несколько корней, то неизвестно к какому из них сходится дихотомия. Метод не применим к корням четной кратности.
Метод применим к корням нечетной кратности, но хуже устойчив к ошибкам округления. Метод не применим к системам уравнений.
§12. Метод простой итерации для решения алгебраических и трансцендентных уравнений.
ТЕОРЕМА 1. (Принцип Банаха сжимающихся отображений).
Пусть R
– полное
метрическое
пространство.
Если
сжатие, то для
него существует
в R
единственная
неподвижная
точка, к которой
сходится итерационный
процесс.
,
где
- произвольный.
План доказательства.
– фундаментальная
(*)
q – коэффициент сжатия
.
Т.к. R – полное метрическое пространство, то в нем всякая фундаментальная последовательность сходится.
– сходится,
,
причем
,
т.е.
– неподвижная
точка.
– единственна.
ЧТД.
- последовательность
приближения
к решению уравнения

Метод
– метод
простой итерации.
Если
в (*)
зафиксировать,
а
,
то
– оценка
погрешности,
оценка скорости
сходимости.
со скоростью
геометрической
прогрессии.
– линейная
скорость сходимости.
Метод простой итерации имеет линейную скорость сходимости.
Пусть
(2),
– вещественная
функция.
Необходимо
привести к виду
.
,
- знакопостоянная
непрерывная
функция.



Условие сходимости для данного метода:
ТЕОРЕМА 2.
Пусть выполняются условия:
Функция
– определена
и непрерывна
на отрезке
и на этом отрезке
удовлетворяет
условию Липшица:
;Для начального приближения
выполняется
условие
;Числа
связаны условием
.
Тогда
уравнение
имеет единственное
решение
в области
,
к которому
сходится итерационный
процесс
со скоростью
сходимости
.
Теорема доказывается аналогично теореме Банаха с точностью до обозначений.
Замечание. Условие Липшица применять трудно, вместо него применяют другое условие:
на отрезке

.
Метод итерация дает бесконечную последовательность приближений, поэтому используют следующие правила остановки:
- по соседним приближениям
задается
уровень останова
и момент останова
n
задается формулой

- по невязке
задается
уровень
и момент останова
n
итерационной
процедуры
задается
неравенствами

Метод простой итерации удобен в использовании, так как он легко программируется на ЭВМ.
Недостаток: невысокая скорость сходимости, т.е. линейная.
§13. Метод Ньютона. Решение уравнений с одной переменной.
Пусть
требуется
решить уравнение
(1),
где функция
– дважды
непрерывно-дифференцируема
на
;
на
и
и
.
Из
этих условий
вытекает, что
на
функция имеет
только один
корень.
Прежде,
чем использовать
итерации, необходимо
(1) привести к
виду
.
.
Функция
непрерывная
в окрестности
корня
уравнения (1).
Следовательно,
уравнение (1) и
уравнение
(2)
будут иметь
один и тот же
корень
.
В
качестве
выберем
,
тогда
(3)
Выберем
начальное
приближение
достаточно
близкое к
.
Остальные
приближения
получаются
по формуле:
(4)
Метод, определенный (4), называется методом Ньютона.
Докажем, что метод Ньютона сходится и получим его оценку погрешности.
|
Если
дано, что
|
|
|
|
|
Докажем, что (4) сходится.
Для
этого покажем,
что отображение
– сжатие, где
.
.
При
получим
.
По непрерывности
функции
на
существует
такая окрестность
точки
,
что для
,
,
а этом сжатие.
Поэтому к
отображению
можно применить
принцип
сжатыхотображений.
Если выбрать
,
то
будет сходиться
к точному решению
уравнения (1).,
т.е.
.
Заметим, что
метод (4) будет
сходиться, если
начальное
приближение
будем выбирать
из окрестности

,
.
Докажем, что метод Ньютона сходится.
Определим
скорость сходимости
метода Ньютона.
Для этого
разложим в ряд
Тейлора в точке
.
.
При
имеем
.
Поэтому

Выразим
(5)
Обозначим
через
,

(6)
,
скорость сходимости
метода Ньютона
квадратичная,
.
Потребуем,
чтобы начальное
условие
выбиралось
из условия
(7)
Тогда из (6) получим


- оценка
погрешности.
Метод Ньютона имеет квадратичную скорость сходимости. Это означает, что при переходе от одной итерации к другой количество верных знаков удваивается в последующем приближении.
Достоинство: высокая скорость сходимости, легко программируется на ЭВМ.
Недостатки: узкая область сходимости.
Если будем
решать операторное
уравнение
,
то на каждом
шаге необходимо
находить значение
обратного
оператора
.
Геометрический смысл метода Ньютона.
П

усть
требуется
решить уравнение
и единственный
корень этого
уравнения
находится на
.
В точке
проведем касательную
к графику функции
,
уравнение
касательной:
.
Если
,
то
– первое
приближение
к
уравнения (1)
по методу Ньютона.
Возьмем
и проведем
касательную
в этой точке.
Получим
.
Если
,
то
– второе
приближение
к
уравнения (1)
по методу Ньютона.
И так далее. Отсюда метод Ньютона называют методом касательных.
§14. Метод хорд. Метод секущих.
По прежнему
решаем уравнение
(1),
где
,
на
и
.
Т.е. на
(1) имеет только
один корень.
Уравнение
(1) запишем в виде

,
где
– символ Ландау: