книги / Численные методы. Ч. 1

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

	К - XL *Ро1х - 4	Ро = i z i
где kmin.A.max	наименьшее и наибольшее	собственные значения матрицы В_|А;
п - номер итерации.

Контрольные вопросы и задания

♦Какие методы решения системы линейных алгебраических уравнений называются прямыми и итерационными?

♦Сформулируйте условия существования и единственности решения системы линейных алгебраических уравнений.

♦Сформулируйте условия разрешимости системы линейных алгебраических уравнений методом Гаусса.

♦ Покажите, какую структуру будут иметь матрицы, равные произведениям

А 'В. АВ"‘ если А и В являются обратимыми верхними (нижними)

треугольными матрицами.

♦Как можно вычислить определитель матрицы коэффициентов, используя процедуру метода Гаусса?

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

♦Выбор "главного" элемента при использовании метода Гаусса возможен с помощью перестановки либо строк, либо столбцов. Обоснуйте, какой вариант предпочтителен.

♦Сформулируйте условия применимости метода "квадратного корня" для решения системы линейных алгебраических уравнений.

♦Сравните методы Гаусса и квадратного корня для решения системы линейных алгебраических уравнений. Укажите достоинства и недостатки каждого из этих методов.

♦Сформулируйте понятие устойчивости системы линейных алгебраических уравнений.

♦Чему равно и что характеризует число обусловленности системы линейных алгебраических уравнений?

♦Определите смысл условия ||5А||<||а ' ,|| ' теоремы 2.3 .

♦ Какую погрешность, относительную у у или абсолютную ||бх||, целесообразно

IM

оценивать при выполнении вычислений на ЭВМ?

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

♦Укажите геометрический смысл сходимости (расходимости) решения системы алгебраических уравнений при использовании итерационных методов.

♦Дайте определение понятия скорости сходимости итерационного процесса.

♦Обоснуйте идею и поясните условия применимости метода Якоби.

♦Обоснуйте идею и поясните условия применимости метода Зейделя.

♦ Покажите, что из условия В - 0.5тА > 0 теоремы 2.4 следует существование

обратной матрицы В*1.

♦Докажите справедливость неравенства (Dx, х) > 0. использованного при доказательстве следствия 1 из теоремы 2.4.

♦Укажите условия применимости метода верхней релаксации.

♦Сформулируйте условия сходимости стационарного итерационного метода.

♦Сформулируйте задачу, решение которой приводит к построению полинома Чебышева на отрезках [-1. 1] и [а, Ь].

♦В чем преимущество метода решения системы линейных алгебраических уравнений с чебышевским набором параметров?

♦Опишите порядок выбора итерационных параметров в методе минимальных невязок.

♦Опишите порядок выбора итерационных параметров в методе минимальных поправок.

♦Опишите порядок выбора итерационных параметров в явном методе скорейшего спуска.

♦Опишите порядок выбора итерационных параметров в неявном методе скорейшего спуска.

3 Н Е Л И Н Е Й Н Ы Е У Р А В Н Е Н И Я

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

нуль:

f(xk) = 0.

(3.1)

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

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

Методы вычисления корней нелинейного уравнения1

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

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

Пусть функция f(x) непрерывна на отрезке [хо,х,]. Процедура метода заключается в последовательном сокращении длины отрезка для локализации корня уравнения (3.1). Первоначально проверяются значения заданной функции на концах отрезка. В случае, если

f(xo)f(x,) = 0.

один из концов отрезка явЛЛется искомым корнем уравнения.

Пусть на концах отрока значения функции имеют разные знаки, то есть имеет место соотношение

f(x„)f(x,)< 0 .

Дополнительно мсто/Лл решали нелинейных уравнений рассматриваются в разделе, посвященном интерполяции фуАций.

2 Встречаются иные назвгйня этого метода - метод бисекции, дихотомии.

х0+х, Вычисляется значение аргумента в середине отрезка, х2 = ^ , и вычисляется

значение функции f(x2) в этой точке. Далее сравниваются знаки функции в точке х2 и, например, в левой точке х0 отрезка.

Если имеет место соотношение f(x0)f (x 2)< 0 (рис. 3.1), то корень следует искать на отрезке [х0,х 2]. В противном случае - корень разыскивается на отрезке [х2,х,]. В результате выполненной операции исходный отрезок сократился вдвое.

Рис. 3.1. Схема метода половинного деления

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

X, + хп, f(xj)-f(x„)<0;

2

•f(x2) 'f(x«)>0'

и так далее.

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

если функция достаточно “пологая”, имеет смысл использовать условие (рис.3.2а)

|хк+, - х к|< 8„;

- если функция “круто” меняет свое значение, целесообразно применять условие (рис.3.2Ь)

|У|ы|<6 у-

В случае, если заранее неизвестен характер “поведения” функции, имеет смысл

использовать одновременно оба условия для прекращения итерационного процесса.

Метод простых итераций

Этот метод заключается в замене уравнения (3.1) эквивалентным ему уравнением

вида
= <р(х).	(3.2)
После этого строится итерационный процесс
х<»«> =	(3.3)

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

f(x) = f(x) + x-x = О, х = х + f(x) = ф(х).

Если в выражении (3.2) положить ф(х) = x + xf(x), можно получить стандартный

вид итерационного процесса для поиска корней нелинейного уравнения:

(П+1) _ Y^11) I .

Ь = г - - ' И - ° -

Рассмотрим отрезок длиной 2г с центром в точке а: А = {х | |х - а| £ г}.

Теорема 3.1. Если функция <р(х) на отрезке А удовлетворяет условию Липшица1с

константой 0 < С < 1, причем
	|< р(а)-а|^(1 -С )г,	(3.4)
то уравнение (3.2) имеет	на отрезке А единственное решение х,	метод простой
итерации х(п+,) = <р(х(п)) сходится к х при любом х(0) € А и имеет место оценка
	|x(N)- x |^ C N|x(0)- x |.	(3.5)
Доказательство.
Докажем “по индукции”, что определяемые в соответствии с		формулой (3.2)
величины x(n) eA V n .
х(0) е А по условию теоремы.
Пусть х(п) еА ; покажем, что и x(lkfI) еА .
В силу х(п+,) = <р(х(п)j	имеем
х1"*11- а = ф(х<п|) - а = ф(х(">)- а + ф(а) - ф(а) = (ф(х'*)) - ф(а))+(ф(а) - а),
|х(.-|| _ а| s	ф(а)| + |ф(а) - а| й С • |х(п| - а|+(1 - С) • г<.С • г+(1 - С) • г = г,

тоесть х(п+1) еА .

Теперь оценим разность получаемых решений для произвольного п: |Х(.-И) - х(п,| = |ф(Х(п)) —ф(х<п",)jj £ С • |х(п) - х (п-"|.

Отсюда получаем

|х(п+1. _ х(")|^с.|х("> - x (“- " |s C 2.|x("-') - х ("“2,|^ ...^ С "-|х (,) - х (в)|.

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

‘Липшиц	Рудольф Отто Сигюмунд [14.5.1832 - 7.10.1903] - немецкий математик. С 1864 года
является профессором Боннского университета. В		1900	году избран	членом	корреспондентом
Парижской академии наук.
Функция	удовлетворяет условию Липшица	на	отрезке [а,	Ь], если	V x,,x2 e[a, b]

|ф(х2) - ф(х,)| £ С|х2 —Х,|, С > 0 - константа [8].

xtp) _ x<4) = |x (p)	- x l,)) = (xtp) - x tp",))+ (x (*’l) - x (p”2))+ (x (p-2) - x (4)) =
= ... = f (x<k+l,- x <k)),
k-qV
L(P) _ x(q)| s g | x<^> _ x»>|s |xo _ x<°>gCk ^ ' W t c - z		' c	* =
k-q	k-ч	k-0
= |x<" - x«j C4	(l + C +C 2 + ... + C « - ') = |x"' - x » |. C’ l- ^	g -	S|x(I>- x < « > |£ .

При выводе последнего соотношения использована формула для суммы членов геометрической прогрессии со знаменателем С, а также условие, что 0 < С < 1, и тем более 0 < С1"-4 <1. р > q .

Очевидно, что при p,q -> оо имеет место

|х(р) - х <ч)|-> 0 ,

и в соответствии с признаком Больцано - Коши1

Зх* е А, limx(n)=x*

п-»®

Переходя к пределу в соотношении x(n+,) = <p(x(n)), в силу непрерывности функции

ф(х) получаем

х* = Нш x(n+,) = lim ср(х(п)) = ф(х*),

П—>0О

n—frao V

/

V /

то есть х* = х - решение уравнения (3.2).

■Больцано Бернард [5.10.1781 18.12.1848] - чешский математик, философ, теолог. В 1800 году закончил философский, а в 1805 - теологический факультеты Пражского университета. В этом же университете с 1805 года возглавлял кафедру истории религии, откуда был уволен в 1820 году з вольнодумство и лишен права публичных выступлений. После этого занимался исследованием в области логики и математики.

Коши Огюстен Луи [21.8.1789 23.5.1857] французский математик. В 1807 году окончил Политехническую школу', в 1810 юлу - Школу мостов и дорог в Париже. С 1810 по 1813 годы работал инженером в Шербурге. С 1816 года был избран членом Парижской академии наук. С 1816 по 1830 год преподавал в Политехнической школе и в Коллеж де Франс. С 1831 года стал иностранным почетным членом neTq>6yprcKofi академии наук. В 1848 году начал преподавать в Парижском университете.

Признак сходимости числовой последовательности Больцано-Коши [8]: для того, последовательность вещественных чисел имела конечный предел, необходимо и достаточно, чтобы х1р; - х(ч) -> 0 при p,q -> оо.

Теперь	покажем,	что получаемое решение единственно. В самом деле, пусть
= ф(х ),	= <р(х~)	- два различных решения уравнения (3.2). Тогда

Iх’ - х~ |= |ф(*’)-ч>(х~12 СК - х" |•

что может иметь место при условии 0 < С < 1лишь в случае х* = х~

Оценим погрешность метода простой итерации после выполнения N итераций: |x‘Nl - х| = |<p(x,N- " ) - ф(х)|sCjxIN‘" - x |s C , |x,N' J1 - х| <;...,

откуда получаем:

|x(N) - x |^ C N|x(0) -х |.

Что и требовалось доказать.

Следствие 1. Если |ф'(х)| < С < 1 Vx € А , а также имеет место соотношение |<р(а)- а| S (1 - С)- г, х(0) <=А ,

то уравнение (3.2) имеет единственное решение, метод простых итераций сходится и имеет место оценка (3.5).

Действительно, согласно теореме Лагранжа1,

|ф(Ь) - ф(а)| = |ф'(^Хь - а)| = |ф'(01'|Ь а| й тах)ф '(^)| •|b - а|.

то есть в качестве константы условия Липшица можно принять

с= тах)ф '(^.

Вэтом случае условия теоремы (3.1) выполняются и все ее утверждения имеют

место.

1 Лагранж Жозеф Луи [25.11.1736 - 10.4.1813] - французский математик и механик. В 1755 году стал профессором Туринской артиллерийской школы. В 1759 году был избран членом Берлинской академии наук. С 1766 года был директором Математического класса Берлинской академии наук, с 1772 года - членом Парижской академии наук, с 1776 года - иностранным почетным членом Петербургской академии наук. В 1795 году стал профессором Парижской Нормальной школы, с 1797 года профессором Политехнической школы.

Теорема Лагранжа [10]: если функция f(x) непрерывна в замкнутом интервале [a, bj и дифференцируема во всех его внутренних точках, то внутри этого интервала существует хотя бы одна

сй f(b)-f(a)

точка для которой--------------

= I (£).

Ь- а