Быков А.Ю. Лекции по вычислительной математике - файл n1.doc

Быков А.Ю. Лекции по вычислительной математике
скачать (434.8 kb.)
Доступные файлы (1):
n1.doc1882kb.01.12.2008 11:01скачать

n1.doc

  1   2   3   4
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ
Быков А. Ю.
Вычислительная математика

учебное пособие по дисциплине «Вычислительная математика»

для подготовки бакалавров технических наук

по направлению 552800 «Информатика и

вычислительная техника»

Москва 2005

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ
Утверждаю УМС МГГУ

в качестве учебного пособия

Быков А. Ю.
Вычислительная математика

учебное пособие по дисциплине «Вычислительная математика»

для подготовки бакалавров технических наук

по направлению 552800 «Информатика и

вычислительная техника»

Москва 2005

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

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

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

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

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

Благодаря компьютерам стало возможным рассматривать вероятностные модели, требующие большого числа пробных расчетов, имитационные модели, которые отражают моделируемые свойства объекта без упрощений (например, функциональные свойства телефоннойАсети).
Глава 1. Теория погрешностей
1.1. Общие сведения об источниках погрешностей, их классификация

Источниками возникновения погрешности численного решения задачи являются:

неточность математического описания, в частности, неточность задания начальных данных;

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

1.1.1. Виды погрешностей

Неустранимая погрешность состоит из двух частей:

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

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

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

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

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

1.1. Модель математического маятника


Рассмотрим простой пример, иллюстрирующий описанные ранее виды погрешностей, на основе задачи описания движения маятника (рис. 1.1), в которой требуется предсказать угол отклонения маятника от вертикали 0, начинающего движение в момент времени t = t0.


Движение маятника может быть описано дифференциальным уравнением второго порядка:

(1.1)

где l - длина маятника, gускорение свободного падения, µ— коэффициент трения.

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

1.2. Абсолютная и относительная погрешности. Формы записи данных

Определение 1.1. Если а - точное значение некоторой величины и а * — известное приближение к нему, то абсолютной погрешностью приближенного значения а* называют некоторую величину (а*), про которую известно, что
|а*- a| ? ?(a*). (1.2)

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

(1.3)

Относительную погрешность часто выражают в процентах.

Определение 1.3. Значащими цифрами числа называют все цифры в его записи, начиная с первой ненулевой слева.

Пример 1.1.
а* =0.03045 а* =0.03045000
Определение 1.4. Значащую цифру называют верной, если модуль погрешности числа не превосходит единицы разряда, соответствующего этой цифре.

Пример 1.2.

а* = 0.03045 ?(a*)=0.000003

а * = 0.030450000 ?(а*) = 0.00000007

Определение 1.5. Число записано со всеми верными цифрами, если в его записи представлены только верные значащие цифры.

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

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

а1 ? а? а2

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

Информацию о том, что а* является приближенным значением числа а с абсолютной погрешностью ?(а*), принято также записывать в виде:

а = а*± ?(а*). (1.4)

Числа *, ?(*) принято записывать с одинаковым числом знаков после запятой.

Пример 1.3.


Информацию о том, что а* является приближенным значением числа а с относительной погрешностью, записывают в виде:


Пример 1.4.

1.123·(1-0.003) ? а ? 1.123·(1+0.003)
1.3. Вычислительная погрешность

Далее для краткости будем обозначать абсолютную погрешность числа x как ех, относительную погрешность - ?x.

Погрешность суммирования чисел

• абсолютная погрешность



• относительная погрешность



Погрешность вычитания чисел:

• абсолютная погрешность



• относительная погрешность



Погрешность умножения чисел

• абсолютная погрешность



• относительная погрешность


Погрешность деления чисел

• абсолютная погрешность



• относительная погрешность



Погрешность функции, зависящей от одной переменной:

• абсолютная погрешность




• относительная погрешность





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

Для представления чисел в памяти компьютера применяют два способа.

Пусть в основу запоминающего устройства положены однотипные физические устройства, имеющие r устойчивых состояний, называемых регистрами. Причем каждому устройству ставится в соответствие одинаковое количество k регистров и, кроме того, с помощью регистров может фиксироваться знак. Упорядоченные элементы образуют разрядную сетку машинного слова: в каждом разряде может быть записано одно из базисных чисел 0,1,..., r-1 (одна из r "цифр" r-ой системы счисления) и в специальном разряде отображен знак "+" или "-". При записи чисел с фиксированной запятой кроме упомянутых r параметров (основания системы счисления) и k (количество разрядов, отводимых под запись числа) указывается еще общее количество l разрядов, выделяемых под дробную часть числа. Таким образом, положительное вещественное число a, представляющее собой в r-ой системе бесконечную, непериодическую дробь, отображается конечной последовательностью





где

т.е.

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

Пример 1.5. Рассмотрим запоминающее устройство с фиксированной запятой, состоящее из k=7 элементов и имеющее r=10 (r =0, 1,..., 9). Будем считать, что общее количество разрядов, выделяемых под дробную часть, l = 3, под знак - один разряд, под целую часть - три разряда (рис. 1.2)








Рис. 1.2. Схема машинного слова запоминающего устройства с фиксированной запятой


Тогда наибольшее число, которое можно сохранить в данном запоминающем устройстве, равно 999.999, а наименьшее равно -999.999. У любого числа из указанного диапазона, являющегося бесконечной периодической дробью, вне зависимости от его величины после запятой сохраняется толь­ко 3 цифры. Поэтому абсолютная точность представления чисел а1 = 1.123456 и а2 = 999.123456 оказывается одинаковой.





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





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


где r - основание, р - порядок, M- мантисса . Если под мантиссу выделяется l

r - ичных элементов, а под порядок - m, то в системе записи с плавающей запятой вещественное число а представляется конеч­ным числом



где ? — целое число из промежутка

Структура машинного слова запоминающего устройства с плавающей запя­той представлена на рис. 1.3.


Знак порядка

Порядок числа разрядов)

Знак мантиссы

Мантисса числа

( разрядов)


Рис. 1.2. Схема машинного слова запоминающего

устройства с плавающей запятой

Числа определяют границы допустимого числового диапазона. Относительная точность представления вещественных чисел равна





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

Например, для записи числа в 48-разрядном машинном слове БЭСМ-6 40 двоичных разрядов выделялись под мантиссу, 6 — под порядок числа и 2 — под знаки мантиссы, т. е. r =2, l = 40, т = 6. Следовательно, точность представления чисел с плавающей запятой не хуже 2-39 (?1012), граница машинного нуля 2-64 (?10-19), машинной бесконечности 263.

Пример 1.6. Рассмотрим запоминающее устройство, состоящее из k= 8 элементов и имеющее r = 10 (r = 0, 1,..., 9). Будем считать, что общее количество разрядов, выделяемых под дробную часть l= 5, под знак порядка числа - 1 ячейка, под знак мантиссы числа — 1 ячейка, под порядок — 2 ячейки.

Оценим точность представления чисел а1 = 1.123123 и ?2 = 999.123123.

Запишем числа в форме представления с плавающей запятой:

a1 =0.1123123.101,

a2 = 0.999123123103.

В запоминающем устройстве числа a1 ,?2 будут записаны в виде, показанном на рис. 1.4.




Рис 1.4. Представление чисел а1, а2 с плавающей запятой

в запоминающем устройстве



Абсолютные погрешности чисел равны:



Относительные погрешности чисел равны:


Глава 2. Решение уравнений с одной переменной

2.1. Общие сведения и основные определения

Наиболее общий вид нелинейного уравнения:

F (x) = 0 (2.1)

где функция F(x) определена и непрерывна на конечном или бесконечном интервале [a, b].

Определение 2.1. Всякое число ?[а,b] , обращающее функцию F(x) в нуль, называется корнем уравнения (2.1).

Определение 2.2. Число ? называется корнем k-ой кратности, если при x=? вместе с функцией F(x) равны нулю ее производные до (k-1)-го порядка включительно:
(2.2)
Определение 2.3. Однократный корень называется простым.

Определение 2.4. Уравнения F(x)=0 и G(x)=0 называются равносильными (эквивалентными), если множества решений данных уравнений совпадают.

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

Определение 2.5. Уравнение (2.1) называется алгебраическим, если функция F(x) является алгебраической.

Путем алгебраических преобразований из всякого алгебраического уравнения можно получить уравнение в канонической форме:

(2.3)

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

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

Определение 2.6. Уравнение (2.1) называется трансцендентным, если функция F(x) не является алгебраической.

Определение 2.7. Решить уравнение (2.1) означает:

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

  2. Определить число корней уравнения.

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



2.2. Отделение корней


Определение 2.8. Отделение корней — процедура нахождения отрезков, на которых уравнение (2.1) имеет только одно решение.

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

(т. е. F(a)∙F(b) < 0), то уравнение (2.1) имеет на этом отрезке по меньшей мере один корень;



2.3. Метод половинного деления


Пусть уравнение (2.1) имеет на отрезке [а, b] единственный корень, причем функция F(x) на данном отрезке непрерывна (рис. 2.1).

Разделим отрезок [а, b] пополам точкой с = (а + b)/2. Если F(с)0, то возможны два случая:

Функция F(x) меняет знак на отрезке [а, с].

Функция F(x) меняет знак нa отрезке [с, b].

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


Рис 2.1. К объяснению метода половинного деления

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


Заменим уравнение (2.1) равносильным уравнением:

x = f (x) (2.4)

Пусть ? — корень уравнения (2.4), а x0 — полученное каким-либо способом нулевое приближение к корню ?. Подставляя x0 в правую часть уравнения (2.4), получим некоторое число x1= f (x1). Повторим данную процедуру с x1 и получим x2 = f (x1). Повторяя описанную процедуру, получим последовательность
x0, x1,...,xn,..., (2.5)

называемую итерационной последовательностью.

Геометрическая интерпретация данного алгоритма представлена на рис. (2.5)

Итерационная последовательность, вообще говоря, может быть как сходящейся, так и расходящейся, что определяется видом функции f(x)



Рис. 2.5. К объяснению метода простой итерации
]Теорема 2.1. Если функция f(x) непрерывна, а последовательность (2.5) сходится, то предел последовательности (2.5) является корнем уравнения (2.4).

Действительно, пусть. Перейдем к пределу в равенстве

(2.6)

Условие сходимости итерационного процесса определяется следующей теоремой.

Теорема 2.2. Достаточное условие сходимости итерационного процесса. Пусть уравнение x =f(x) имеет единственный корень на отрезке [a,b] и выполнены условия:

  1. f(x) определена и дифференцируема на [a,b].

  2. f(x) [a,b] для всех x [a,b].

  3. Существует такое вещественное q, что <1для всех x [a,b].

Тогда итерационная последовательность сходится при любом начальном приближении xo [a,b].

Доказательство. Построим итерационную последовательность вида (2.5) с любым начальным значением xo [a,b]. B силу условия 2 теоремы 2.2 все члены последовательности находятся в отрезке [a,b].

Рассмотрим два последовательных приближения хп = f(xn-1) и xn+l =f(xn). По теореме Лагранжа о конечных приращениях имеем:



Переходя к модулям и принимая во внимание условие 3 теоремы 2.2, получим:





При n = 1, 2, имеем:



(2.7)


Рассмотрим ряд

(2.8)

Составим частичные суммы этого ряда



Заметим, что (n+1)-я частичная сумма ряда (2.8) совпадает с n-ым членом итерационной последовательности (2.5), т. e.

Sn+1=xn. (2.9)

Сравним ряд (2.8) с рядом

(2.10)

Заметим, что в силу соотношения (2.7) абсолютные величины членов ряда (2.8) не превосходят соответствующих членов ряда (2.10). Ho ряд (2.10) сходится как бесконечно убывающая геометрическая прогрессия (q. B силу непрерывности функции f получаем

(см. (2.6)):



т.е. ? — корень уравнения x = f(x).

Отметим, что условия теоремы не являются необходимыми. Это означает, что итерационная последовательность может оказаться сходящейся и при невыполнении этих условий.
Отыщем погрешность корня уравнения, найденного методом простой итерации. Пусть xn -приближение к истинному значению корня уравнения x=f(x). Абсолютная ошибка приближения xn оценивается модулем



Принимая во внимание (2.8) и (2.9), имеем

(2.11)

Сравним (2.11) с остатком ряда (2.9):

(2.12)

Учитывая оценку (2.7), получаем



Таким образом, для оценки погрешности n-го приближения получается формула





(2.13)
Ha практике удобнее использовать модификацию формулы (2.13).

Примем за нулевое приближение xn-1 (вместо x0). Следующим приближением будет хп

(вместо x1). Так как то




(2.14)
При заданной точности ответа ? итерационный пpоцеcc прекращается, если

2.5. Преобразование уравнения к итерационному виду

Уравнение F(x) = 0 преобразуется к виду, пригодному для итерационного процесса, следующим образом:

x = x-mF(x),

где mотличная от нуля константа.

B этом случае

F(x) = x-mF(x). (2.15)

Функция f(x) должна удовлетворять условиям теоремы 2.2. Дифференцируя (2.15), получим
f'(x) = 1-mF(x). (2.16)
Для выполнения условия 3 теоремы 2.2 достаточно подобрать m, так чтобы для всех x[a,b]
(2.17)
Глава 3. Методы решения систем линейных алгебраических уравнений

3.1. Общие сведения и основные определения

Рассмотрим систему, состоящую из m линейных алгебраических уравнений с n неизвестными:




,



,


(3.1)

которая может быть записана в матричном виде

Ax = b, (3.2)

где A — прямоугольная матрица размерности mЧn:

(3.3)
xвектор n-го порядка:



b - вектор m-порядка:


Определение 3.1. Решением системы (3.1) называется такая упорядоченная совокупность чисел x1=c1, х22, ... , хnn, которая обращает все уравнения системы (3.1) в верные равенства.

Определение 3.2. Прямыми методами решения систем линейных уравнений называются методы, дающие решение системы за конечное число арифметических операций. Если отсутствуют ошибки округления, то получаемые решения всегда являются точными.

Определение 3.3. Итерационными методами решения систем линейных уравнений называются методы, дающие решение системы уравнений как предел последовательности приближений, вычисляемых по единообразной схеме.
3.2. Метод Гаусса

Р


,



,
ассмотрим систему линейных алгебраических уравнений
(3.4)


при условии, что матрица A = (aij) невырождена.

Метод Гаусса состоит в преобразовании системы (3.4) последовательным исключением переменных к равносильной системе с треугольной матрицей






… … …




(3.5)

Затем из системы (3.5) последовательно находят значения всех неизвестных.

Таким образом, процесс решения системы (3.4) распадается на два этапа:

  1. Прямой ход — приведение системы (3.4) к треугольному виду.

  2. Обратный ход — нахождение значений неизвестных переменных, в соответствие с (3.5).


3.3. Вычисление определителей

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

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

Пусть задана квадратная матрица X n-го порядка:

. (3.6)

Представим матрицу X в виде:

X=Y·Z, (3.7)

где

(3.8)
Известно, что определитель матрицы равен произведению определителей:

|X|=|Y|∙|Z| (3.9)

но |Z|= 1, поэтому

|X|=y11y22∙…∙ynn. (3.10)

Формулы для вычисления элементов матриц Y и Z получаются перемножением этих матриц и приравниванием элементов матрицы Y к соответствующим элементам матрицы X:


при (3.11)

(3.12)

3.4. Решение систем линейных уравнений методом простой итерации

Запишем исходную систему (3.4) в следующем виде:







(3.13)

или сокращенно

(3.14)

где i= l,2,...n.

Правая часть (3.14) определяет отображение F


(3.15)

преобразующее точку n-мернего векторного пространства в точку того же пространства. Используя систему (3.4) и выбрав начальную точку

можно построить итерационную последовательность точек n-мерного пространства (аналогично методу простой итерации для скалярного уравнения x = f(x));

(3.16)

Оказывается, что при определенных условиях последовательность (3.16) сходится и ее предел является решением системы (3.13). Предваряя обсуж­дение данных условий, напомним необходимые сведения из математическо­го анализа.

Определение 3.4. Функцию (x,y), определяющую расстояние между точками x и у множества X, называют метрикой, если выполнены следующие условия:

1.. (x,y) ?0.

  1. (x,y) = 0 тогда и только тогда, когда x = у.

  2. (x,y) =(y.x).

  3. (x,z)? (x,y)+ (y,z).

Определение 3.5. Множество с введенной в нем метрикой становится метрическим пространством.

Определение 3.6. Последовательность точек метрического пространства называется фундаментальной, если для любого ?>0 существует такое число ?(?), что для всех m, n > N выполняется неравенство т,х„)<?

Определение 3.7. Пространство называется полным, если в нем любая фундаментальная последовательность сходится.

Пусть Fотображение, действующее в метрическом пространстве E с метрикой , x и у — точки пространства E, a Fx, Fy — образы этих точек.

Определение 3.8. Отображение F пространства E в себя называется сжимающим отображением, если существует такое число (0, 1), что для любых двух точек x, у выполняется неравенство

(Fx,Fy)??(x,y). (3.17)
Определение 3.9. Точка x называется неподвижной точкой отображения F, если Fx = x.

Аналогично одномерному случаю можно доказать теорему о достаточном условии сходимости итерационного процесса в n-мерном пространстве. (Доказательство теоремы приводится практически во всех учебниках, по­священных численным, методам, например,[1].)

Теорема. 3.1. Если F- сжимающее отображение, определенное в полном метрическом пространстве, то существует единственная неподвижная точка x, такая что x = Fx. При этом итерационная последовательность, построенная для отображения F с любым начальным членом x(0), сходится к x.

B ходе доказательства данной теоремы показывается, что

(3.18)

Приняв k-oe приближение за нулевое, из (3.18) получаем полезное для приложений неравенство:

(3.19)

Рассмотрим условия, при которых отображение (3.15) будет сжимающим. Как следует из определения (3.17), решение данного вопроса зависит от способа метризации данного пространства. Обычно при решении систем линейных уравнений используют одну из следующих метрик:

(3.20)

(3.21)

(3.22)
Для того чтобы отображение F, заданное в метрическом пространстве уравнениями (3.15), было сжимающим, достаточно выполнения одного из следующих условий:
1. B пространстве с метрикой р1:




2. В пространстве с метрикой р2:

3. B пространстве с метрикой р3:

< 1. (3.25)

Для установления момента прекращения итераций при достижении заданной точности может быть использована, например, формула, следующая из (3.19):

(3.26)

Алгоритм решения системы методом итераций реализуется следующим образом:

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

  2. Разделите каждое уравнение на соответствующий диагональный коэффициент.

3.. Проверьте выполнение условий (3.23) - (3.25).

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

  2. Реализуйте итерационный процесс (обычно за начальное приближение берется столбец свободных членов).

Пример 3.1 Преобразование системы уравнений к виду пригодному для итерационного процесса.




1. Возьмите первым уравнением второе, третьим первое, а вторым - сумму первого и третьего уравнений:




2. Разделите каждое уравнение на диагональный коэффициент и выразите из каждого уравнения диагональное неизвестное:





3.5. Метод Зейделя

Н
(3.27)
апомним, что при решении системы линейных уравнений вычислительные формулы имеют вид:

где i = 1,2,...n.

Из (3.27) видно, что в методе простой итерации для получения нового значения вектора решений на

(i + 1)-ом шаге используются значения переменных, полученные на предыдущем шаге.

Основная идея метода Зейделя состоит в том, что на каждом шаге итерационного процесса при вычислении, значения переменной yi, учитываются уже найденные значения




(3.28)

Достаточные условия сходимости итерационного процесса (3.23) - (3.25) также являются достаточным условиями сходимости метода Зейделя.

Существует возможность автоматического преобразования исходной системы к виду, обеспечивающему сходимость итерационного процесса метода Зейделя. Для этого умножим левую и правую части системы (3.2) на транспонированную матрицу системы АT, получим равносильную систему

C·X=D, (3.29)

где C =ATA, D=ATb

Система (3.29) называется нормальной системой уравнений. Нормальные системы уравнений обладают рядом свойств, среди которых можно выделить следующие:

Последнее свойство дает возможность "автоматически" приводить нормальную систему (3.29) к виду, пригодному для итерационного процесса Зейделя:


(3.30)

г
(3.31)
де


. (3.32)

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

Теорема 3.2. Итерационный процесс метода Зейделя для приведенной системы (3.30), эквивалентной нормальной системе (3.29), всегда сходится к единственному решению этой системы при любом выборе начального приближения [2].

Таким образом, решение произвольной системы линейных уравнений вида (3.1) методом Зейделя реализуется в соответствие со следующим алгоритмом:

  1. Ввод матрицы A коэффициентов исходной системы и вектор столбца свободных членов.

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

3. Приведение нормальной системы к виду, пригодному для итерационного процесса Зейделя(3.30), (3.31).

4. Задание требуемой точности решения.

5. Циклическое выполнение итерационного процесса до достижения требуемой точности.

Глава 4. Методы решения систем нелинейных уравнений
4.1. Векторная запись нелинейных систем. Метод простых итераций
Пусть требуется решить систему уравнений

(4.1)

где f1, f2,…,fn - заданные, вообще говоря, нелинейные вещественнозначные функции n вещественных переменных x1, x2,…,xn.

Введем обозначения:




Тогда систему (4.1) можно заменить одним уравнением

(4.2)

относительно векторной функции F векторного аргумента .

Следовательно, исходную задачу можно рассматривать как задачу о нулях нелинейного отображения B этой постановке данная задача является прямым обобщением задачи о нахождении решения нелинейного уравнения для случая пространств большей размерности. Это означает, что можно строить методы ее решения как на основе обсужденных в предыдущей лекции подходов, так и осуществлять формальный перенос выведенных для скалярного случая расчетных формул. Однако не все результаты и не все методы оказывается возможным перенести формально (например, метод половинного деления). B любом случае следует позаботиться о правомерности тех или иных операций над векторными переменными и векторными функциями, а также о сходимости получаемых таким способом итерационных процессах. Отметим, что переход от n = 1 к n ? 2 вносит в задачу нахождения нулей нелинейного отображения свою специфику, учет которой привел к появлению новых методов и различных модификаций уже имеющихся методов. B частности, большая вариативность методов решения нелинейных систем связана с разнообразием способов, которыми можно решать линейные алгебраические задачи, возникающие при пошаговой линеаризации данной нелинейной вектор функции F(x).

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

Пусть система (4.1) преобразована к следующей эквивалентной нелинейной системе:


(4.3)

или в компактной записи:



(4.4)

Для задачи о неподвижной точке нелинейного отображения Ф: Rn?Rn запишем формальное рекуррентное равенство:


(4.5)


где k определяет метод простых итераций

для задачи (4.3) и k = 0,1,2,...,n.

Если начать процесс построения последовательности (x-(k)) c некоторого вектора и продолжить вычислительный процесс по формуле (4.5), то при определенных условиях данная последовательность со скоростью геометрической прогрессии будет приближаться к вектору - неподвижной точке отображения ?(x).

Справедлива следующая теорема, которую мы приводим без доказательства.

Теорема 4.1, Пусть функция Ф(х) и замкнутое множество таковы, что:

1.

2. <1:

Тогда Ф(x) имеет в M единственную неподвижную точку последовательность (x-(k)), определяемая (4.5), сходится при любом к ; справедливы оценки:



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

Теорема 4.2. Пусть Ф(х) дифференцируема в замкнутом шаре , причем . Тогда если центр и paдиус r шара S таковы, что ,то справедливо заключение теоремы 4.1 с M = S .

Запишем метод последовательных приближений (4.5) в развернутом виде:

(4.6)

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

(4.7)
Заметим, что, как и для линейных систем, отдельные уравнения в (4.7) неравноправны, т. e. перемена местами уравнений системы (4.3) может изменить в некоторых пределах число итераций и вообще ситуацию со сходимоcтью последовательности итераций. Для того чтобы применить метод простых итераций (4.6) или его "зейделеву" модификацию (4.7) к исходной системе (4.1), необходимо сначала тем или иным способом привести эту систему к виду (4.3). Это можно сделать, например, умножив (4.2) на неособенную n Ч n матрицу A и прибавив к обеим частям уравнения -AF вектор неизвестных. Полученная система

(4.8)

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



4.2. Метод Ньютона решения систем нелинейных уравнений

Для решения системы (4.3) будем пользоваться методом последовательных приближений.
Предположим, известно k-e приближение одного из

изолированных корней векторного уравнения (4.2). Тогда точный корень уравнения (4.2) можно представить в виде:

(4.9)

где –поправка (погрешность корня).

Подставляя выражение (4.9) в (4.2), имеем

(4.10)

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

(4.11)

или в развернутом виде,

(4.12)

Из формул (4.11) и (4.12) видно, что под производной следует понимать матрицу Якоби системы функций f1,f2,...,fn относительно переменных т.е.

или в краткой записи



поэтому формула (4.12) может быть записана в следующем виде:

(4.13)

Если det то

(4.14)

Отсюда видно, что метод Ньютона для решения системы (4.1) состоит в построении итерационной последовательности:

(4.15)

гдe k=0, 1, 2,
Если все поправки становятся достаточно малыми, счет прекращается. Иначе новые значения xi используются как приближенные значения корней, и процесс повторяется до тех пор, пока не будет найдено решение или не станет ясно, что получить его не удастся.
4.3. Решение нелинейных систем методами спуска
Общий недостаток всех рассмотренных ранее методов решения систем нелинейных уравнений состоит в локальном характере сходимости, затрудняющем их применение в случаях (достаточно типичных), когда существуют проблемы с выбором начального приближения, обеспечивающего сходимость итерационной вычислительной процедуры. B этих случаях можно использовать численные методы оптимизации - данный раздел вычислительной математики выделяется в самостоятельную дисциплину. Для использования наглядной геометрической интерпретации приводимых ниже рассуждений и их результатов ограничимся, как и в предыдущем пункте, рассмотрением системы, состоящей из двух уравнений с двумя неизвестными

(4.16)

Из функций f(x,y), g(x,y) системы (4.l6) образуем новую функцию

Ф

Так как эта функция не отрицательная, то найдется точка (вообще говоря, не единственная) такая, что

ФФ


Рис. 4.1. Пространственная интерпретация метода наискорейшего спуска для функции (4.17)



Рис. 4.2. Траектория наискорейшего спуска для функции (4.17) в плоскости ХОУ
Следовательно, если тем или иным способом удается получить точку , минимизирующую функцию Ф(x,y), и если при этом окажется, что ФФ, то точка - истинное решение системы (4.16), поскольку

Ф=0

Последовательность точек - приближений к точке минимума функции Ф(х,у) - обычно получают по рекуррентной формуле

(4.18)

где k=0, l, 2,..., - вектор, определяющий направление минимизации, а - скалярная величина, характеризующая величину шага минимизации (шаговый множитель). Учитывая геометрический смысл задачи минимизации функций двух переменных Ф(x,y) - "спуск на дно" поверхности z = Ф(x,y) (рис. 4.1), итерационный метод (4.18) можно назвать методом спуска, если вектор при каждом k является направлением спуска (т. e. существует такое >0, что Ф, и если множитель подбирается так, чтобы выполнялось условие релаксации ?, означающее переход на каждой итерации в точку с меньшим значением минимизируемой функции.

Таким образом, при построении численного метода вида (4.18) минимизации функции Ф(x,y) следует ответить на два главных вопроса: как выбирать направление спуска и как регулировать длину шага в выбранном направлении с помощью скалярного параметра - шагового множителя . Приведем простые соображения по этому поводу.

При выборе направления спуска естественным является выбор такого направления, в котором минимизируемая функция убывает наиболее быстро.

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

Ф=

антиградиент функции Ф(х,у). Таким образом, из семейства методов (4.18) выделяем градиентный метод

(4.19)

Оптимальный шаг в направлении антиградиента - это такой шаг, при котором значение ? наименьшее среди всех других значений Ф(х,у) в этом фиксированном направлении, т.е. когда точка является точкой условного минимума. Следовательно, можно рассчитывать на наиболее быструю сходимость метода (4.19), если полагать в нем

(4.20)

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

Геометрическая интерпретация этого метода хорошо видна на рис. 4.1, 4.2. Характерны девяностоградусные изломы траектории наискорейшего спуска, что объясняется исчерпываемостью спуска и свойством градиента (а значит, и антиградиента) быть перпендикулярным к линии уровня в соответствующей точке.
4.3.1. Метод Ньютона

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

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



где

(4.21)

- матрица вторых производных:




Условие минимума по : . Вычислим градиент из из (4.22) и найдем значение :

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

=. (4.23)

Метод Ньютона реализуется следующей последовательностью действий:
1. 3адается (произвольно) точка начального приближения .

2. Вычисляется в цикле по номеру итерации k=0, 1,:

3. Закончить итерационный процесс, используя одно из условий, описанных в разд. 2.5.

Оценка погрешности метода Ньютона дается формулой



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


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

  1   2   3   4


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации