Xreferat.com » Рефераты по математике » Вычислительные методы алгебры (лекции)

Вычислительные методы алгебры (лекции)

§1. Учет погрешностей вычислений.


При решении математических задач могут возникнуть погрешности по различным причинам:

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

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

  3. Часто исходные данные заданы не точно, а приближенно. При выполнении вычислений погрешность исходных данных в некоторой степени переходит в погрешность результата. Такая погрешность называется погрешностью действий.

  4. Погрешность, возникающая при округлении бесконечных и конечных десятичных чисел, имеющих большее число десятичных знаков, чем надо в округлении, называется погрешностью округления.

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

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

Если , то а взято с недостатком.

Если , то а взято с избытком.

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

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

Пример. Пусть а=0,273 – приближенное значение х с точность до 0,001. Указать границы, в которых заключается х.

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

, α – порядок округления разряда.

Определение. Относительной погрешностью приближенного значения а числа х называется отношение

.

Пример. Округлить до десятых число 27,52 и найти погрешность и относительную погрешность округления:

,

,

.

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

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

Установим связь между границами погрешностей абсолютной и относительной:

- граница относительной погрешности;

- граница абсолютной погрешности.

.


§10. Вспомогательные сведения из функционального анализа.


Определение. Множество Х произвольных элементов называется метрическим пространством, если ставится в соответствие число , удовлетворяющее следующим условиям:

  1. ;

  2. ;

– расстояние между x и y.

1-3 – аксиомы метрики.


Говорят, что множество элементов - метрическое пространство сходится к , если

, .

Последовательность точек называется сходящейся в себе (фундаментальной), если .

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


Определение. Метрическое пространство, в котором всякая фундаментальная последовательность сходится называется полным.


Пример. .

Зададим различными способами расстояния:

  1. кубическая метрика, m-метрика

;

  1. сферическая метрика, метрика

;

  1. октаэдрическая, s-метрика

.

Для всех выполняются аксиомы метрики и в каждой – полное метрическое пространство.


Пусть X,Y – метрические пространства.

называется оператором, заданным в X со значением в Y.

Если X=Y, то – оператор, отображающий Х в себя (преобразование).

Если , то – неподвижная точка при отображении .


Определение. Говорят, что отображение называется сжимающим (сжатием), если .


§11. Решение уравнений с одним неизвестным. Дихотомия.


Пусть требуется решить уравнение (1), где – непрерывная функция.

Число называется корнем уравнения (1), если .

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

Отделить корень уравнения значит найти такой интервал, внутри которого находится один и только один корень данного уравнения.

Для отделения корней можно применить следующий признак:

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

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

Отделить корень можно и графически: нарисовать график и указать точки пересечения с осью Ох.

Совершенный метод отделения корней – метод Штурма.

Дихотомия (метод деления отрезка пополам).

  1. Пусть

существует хотя бы один корень на ;

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

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

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

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

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


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


ТЕОРЕМА 1. (Принцип Банаха сжимающихся отображений).

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

, где - произвольный.

План доказательства.

  1. – фундаментальная

(*)

q – коэффициент сжатия

.

  1. Т.к. R – полное метрическое пространство, то в нем всякая фундаментальная последовательность сходится.

– сходится, , причем , т.е. – неподвижная точка.

  1. – единственна.

ЧТД.


- последовательность приближения к решению уравнения


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

Если в (*) зафиксировать, а , то

– оценка погрешности, оценка скорости сходимости.

со скоростью геометрической прогрессии.

– линейная скорость сходимости.

Метод простой итерации имеет линейную скорость сходимости.

Пусть (2), – вещественная функция.

Необходимо привести к виду .

, - знакопостоянная непрерывная функция.


Условие сходимости для данного метода:

ТЕОРЕМА 2.

Пусть выполняются условия:

  1. Функция – определена и непрерывна на отрезке и на этом отрезке удовлетворяет условию Липшица: ;

  2. Для начального приближения выполняется условие ;

  3. Числа связаны условием .

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

Теорема доказывается аналогично теореме Банаха с точностью до обозначений.

Замечание. Условие Липшица применять трудно, вместо него применяют другое условие:

на отрезке

.

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

  1. по соседним приближениям

задается уровень останова и момент останова n задается формулой

  1. по невязке

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

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

Недостаток: невысокая скорость сходимости, т.е. линейная.


§13. Метод Ньютона. Решение уравнений с одной переменной.


Пусть требуется решить уравнение (1), где функция – дважды непрерывно-дифференцируема на ; на и и .

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

Прежде, чем использовать итерации, необходимо (1) привести к виду .

.

Функция непрерывная в окрестности корня уравнения (1). Следовательно, уравнение (1) и уравнение (2) будут иметь один и тот же корень .

В качестве выберем , тогда (3)

Выберем начальное приближение достаточно близкое к . Остальные приближения получаются по формуле:

(4)

Метод, определенный (4), называется методом Ньютона.

Докажем, что метод Ньютона сходится и получим его оценку погрешности.

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

  • если k=1, то скорость сходимости линейная;

  • если k=2, то скорость – квадратичная;

  • если k=3, то скорость – кубическая;

  • если k>1, то сходимость метода сверхлинейная.


Докажем, что (4) сходится.

Для этого покажем, что отображение – сжатие, где .

.

При получим

.

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

Поэтому к отображению можно применить принцип сжатыхотображений.

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

Заметим, что метод (4) будет сходиться, если начальное приближение будем выбирать из окрестности

, .

Докажем, что метод Ньютона сходится.

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

.

При имеем . Поэтому

Выразим (5)

Обозначим через ,

(6)

, скорость сходимости метода Ньютона квадратичная, .

Потребуем, чтобы начальное условие выбиралось из условия

(7)

Тогда из (6) получим

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

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

Достоинство: высокая скорость сходимости, легко программируется на ЭВМ.

Недостатки: узкая область сходимости.

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

Геометрический смысл метода Ньютона.

П
усть требуется решить уравнение и единственный корень этого уравнения находится на .

В точке проведем касательную к графику функции , уравнение касательной: .

Если , то

– первое приближение к уравнения (1) по методу Ньютона.

Возьмем и проведем касательную в этой точке. Получим .

Если , то

– второе приближение к уравнения (1) по методу Ньютона.

И так далее. Отсюда метод Ньютона называют методом касательных.


§14. Метод хорд. Метод секущих.


По прежнему решаем уравнение (1), где , на и .

Т.е. на (1) имеет только один корень.

Уравнение (1) запишем в виде

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: