А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (2000) (1160081), страница 9
Текст из файла (страница 9)
находится следующее собственное значение.Решение. Разложение по собственным векторам даетi=iи поэтому(ук,ук) =±а}>?кЛъ~К)\1=1(У*+,,</*) = Х>?лГ(А<-А„) 2 .i=i(5.13)5.3. Упражнения75После подстановки этих представлений получим выражение (5.13), которое дает..*-оо(ук+\ук)_.(j/*,y*)Упражнение 5.5. Покажите, что для вещественной матрицы А и ортогональной матрицы Q имеет место(5- 14 )\\Q4M = И ж .для евклидовой (сферической) нормы:/ пvt=iпJ=Iч ]/2'Решение. Непосредственными выкладками убеждаемся в справедливостиравенствагдеп1г(А) = ]Па,;.i=lПринимая во внимание, что для ортогональной матрицы Q* = Q~\получим\\QA\\2E = tr((QAYQA) =u(A'Q*QA)=tT(A*A).Тем самым имеет место равенство (5.14).Упражнение 5.6. Для симметричной матрицы А постройте матрицу вращения Т(Ы), которая обращает в нуль элемент Ьы матрицы В — Т*(Ы)АТ(Ы).Решение.
Для элементов матрицы вращения Т(Ы) используем обозначенияTkk(k, I) = T„(k, I) = cosO,Tu(k, I) = -Tlk(kl) = - sin в.76Глава 5. Спектральные задачи линейной алгебрыРассмотрим вначале матрицу С = АТц. Она отличается от матрицы Атолько столбцами с номерами к и I:Cik = a,ik cos в + а.ц sine,cit = ~e,ik sin в + a,-j cos в,bij = a,ij, t = l,2,...,n,fc,/^j = l,2,...,n.В силу такого определения элементов матрицы имеемc2ik + cl = a2ik + a2iht=l,2,...,n.(5.15)Аналогично, для элементов матрицы В = Тк1С получимhi = с*, cos в + c(i sin 0,Ьн — —Cki sin# + сц cos б,Cji = bji,г= 1,2,.
. . , n ,* , / ^ j ' = l,2,...,n,причемЬ« + Ь?, = <£• + <&*' = 1 , 2 , . . . , п.(5.16)Полагая г = к,1 в (5.15), (5.16), с учетом симметричности матрицполучимъкк + 2Ь*| + Ьи = акк + 2аы + аи.Для диагональных элементов имеемЪкк — о-кк cos в + ац sin в + 2й)ы cos в sin в,21hi — акк sin в + ац cos в - 2аы cos в sin 6.С учетом этого требование Ьы — О дает намcos20=1-^.г )V{акк ~ аиУ + eti /Отсюда мы и получим выражения для элементов матрицы вращения.5.4. Задачи775.4. ЗадачиЗадача 5.1.
Пусть А], А 2 ) ..., А„ — собственные значения матрицы А.Докажите, чтопАпtru) = 5Z <' <мл) = П А «i=li=lЗадача 5.2. Покажите, что для любых квадратных матриц А и В матрицы АВ и В А имеют одинаковые характеристические многочлены и,следовательно, одни и те же собственные значения.Задача 5.3. Докажите, что при А = А*, В = В* собственные значенияматрицы АВ + В А вещественны, а матрицы АВ — В А чисто мнимые.Задача 5.4. Пусть вещественная матрица S кососимметричная (5 = -S*).Доказать, что матрица преобразования КелиТ = (Е - S)(E + S)~lортогональна.Задача 5.5.
Докажите, что каждое собственное значение положительноопределенной матрицы положительно.Задача 5.6. Пусть А — положительно определенная матрица. Показать,что имеет место неравенство Адамарапdet(vi)< Д о ; , ,t=iпричем равенство достигается тогда и только тогда, когда А — диагональная матрица.Задача 5.7. Доказать следующую оценку для евклидовой нормы матрицы:I>i2<iwiii=lГлава 5.
Спектральные задачи линейной алгебры78Задача 5.8. Пусть при некотором г для всех к ф j выполняются неравенствапп\а.кк ~ ац\ > ] Р l<**jl + 5 3 la,jlПокажите, что круг Гершгоринап|А - ац\ < Yl Ыгф]=\содержит только одно собственное значение.Задача 5.9. Для матрицы А = А*, у которой|А,| < |Л2| < --- < |A«Uдля нахождения А„ используется итерационный процесс (5.7). Установитесходимость ук при к —» оо к собственному вектору <рп.Задача 5.10. Исследуйте итерационный процесс обратных итераций длянахождения собственных значений Ai = А2 и соответствующих собственных векторов, когда|А||>|А3|>--->|АП|.(5.17)Задача 5.11.
Рассмотрите возможности решения частичной проблемызначений для симметричной матрицы А при А| = -А 2 в предположениях (5.17).Задача 5.12. Докажите, что в (?Я-алгоритме все матрицы 4* будут верхними почти треугольными, если верхней почти треугольной являетсяматрица А.Глава 6Нелинейные уравненияи системыМногие прикладные задачи приводят к необходимости нахождения приближенного решения нелинейных уравнений и систем нелинейных уравнений. С этой целью используются итерационныеметоды. Приведены алгоритмы решения нелинейных уравненийс одним неизвестным и систем нелинейных уравнений. Применяются итерационные метод последовательных приближений(простой итерации) и метод Ньютона в различных модификациях.6.1. Решение нелинейных уравнений и системИщется решение нелинейного уравнения/ ( * ) = <>,(6.1)где f(x) — заданная функция.
Корни уравнения (6.1) могут быть комплексными и кратными. Выделяют как самостоятельную проблему разделения корней, когда проводится выделение области в комплекснойплоскости, содержащей один корень. После этого на основе тех илииных итерационных процессов при выбранном начальном приближениинаходится решение нелинейного уравнения (6.1).В более общем случае мы имеем не одно уравнение (6.1), а системунелинейных уравненийД ( х ь а ; 2 , . . . , я п ) = 0,i=l,2,...,n.(6-2)Обозначим через х = {х|,Х2,...,х„} вектор неизвестных и определимвектор-функцию F(x) = {/|, / 2 , . . .
, / „ } . Тогда система (6.2) записываетсяГлава 6. Нелинейные уравнения и системы80Основные обозначения/(*) — функция одной переменнойft(x), i= 1,2,... ,п — функции п переменных(х~ {х,} = {хих2,...,х„})—вектор-функцияF(*) = {fu Л, ••-,/»}с компонентами /i, /г,• • •, /лУ(х) — матрица ЯкобиX* — приближенное решение на fc-ойитерациив виде уравненияF(x) = 0.(6.3)Частным случаем (6.3) является уравнение (6.1) (га = 1). Второйпример (6.3) — система линейных алгебраических уравнений, когдаF(x) = Ax-f.6.2. Итерационные методы решениянелинейных уравненийДля приближенного решения нелинейных уравнений и систем нелинейных уравнений используются итерационные методы. Среди основныхподходов можно выделить метод последовательных приближений (простой итерации) и метод Ньютона.6.2.1.
Алгоритмы для решения нелинейного уравненияПри итерационном решении уравнений (6.1), (6.3) задается некоторое начальное приближение, достаточно близкое к искомому решению х*. В одношаговых итерационных методах новое приближение хк+1 определяетсяпо предыдущему приближению хк. Говорят, что итерационный метод сходится с линейной скоростью, если хк+] -х* = 0(хк -х*) и итерационныйметод имеет квадратичную сходимость, если хк+] - х* — О ((хк - х')2).6.2. Итерационные методы решения нелинейных уравнений81Заменим уравнение (6.1) эквивалентным уравнениемх = <р(х),(6.4)полагая, например,tp{x) = x+g(x)f{x),где функция д(х) не меняет знака на отрезке, на котором ищется решение уравнения (6.1). Для приближенного решения уравнения (6.4)используется метод простой итерации, когдаX= *>(**),* = 0,1,...,(6.5)при некотором заданном начальном приближении х°.Пусть в некоторой окрестности R = {а; | \х - х*\ < г} корня х — х*уравнения (6.4) функция <р(х) удовлетворяет условию Липшица\<p(x)-tp(y)\^q\x-y\x,yeR(6.6)с постоянной q < 1.
Тогда метод простой итерации (6.5) сходится и для погрешности верна оценка(х*-х*| < д*[х°-ж*|.(6.7)Можно сформулировать условия, гарантирующие, что имеется единнный корень в окрестностиокрестственныйначального приближения ж0. Пусть теперьR= {х\\х-х°\^г}и\x°-<p(x°)\<(l-q)r,(6.8)тогда при выполнении (6.6) с q < 1 уравнение (6.4) имеет единственноерешение в R.В итерационном методе Ньютона (методе касательных) для новогоприближения имеемк+{ _ к_»/ (**)*.*+•=* -7Гпк>01* =fc_0,1/f'(x)' Ы == %-(x).^(6.9)Пусть х* — простой вещественный корень уравнения (6.1) и определим R = {х | \х - х*\ ^ г} — окрестность этого корня.
Предположимтакже, чтоinf|/'(i)l = m > 0 ,sup|/"(i)l = M,82Глава 6. Нелинейные уравнения и системыпричемТогда при х° € R метод Ньютона (6.9) сходится и для погрешностисправедлива оценка|ав* - ж * | < в 2 * -1 !* 0 -**|Тем самым метод Ньютона имеет квадратичную сходимость.Модификации метода Ньютона направлены на минимизацию вычислительной работы, на увеличение окрестности корня, в которой можнозадавать начальное приближение.
Примером выступает метод секущих,который получается из метода Ньютона заменой производной в знаменателе на соответствующую разделенную разность:„*+1 _ _*X= X —я*-я*- 1/(«*)-/(х*-«)/(**),* = 0,1,....(6.10)Этот метод является простейшим двухшаговым итерационным методом,когда новое приближение xk+l находится по двум предыдущим хк и ж*-1.6.2.2. Методы решения систем нелинейных уравненийПри приближенном решении систем нелинейных уравнений (6.3) можно ориентироваться на многомерные аналоги метода простой итерациии метода Ньютона. Многие одношаговые методы для приближенногорешения (6.3) по аналогии с двухслойными итерационными методамидля решения систем линейных алгебраических уравнений можно записать в видеВк+1-— + * • ( * * ) = 0,4 = 0,1,...,(6.11)где Tjt+i — итерационные параметры, а Вк+\ — квадратная матрица пхп,имеющая обратную.Для стационарного итерационного метода (6.11) (В и г не зависятот к) имеемхк+] =S(xk),(6.12)6.2.
Итерационные методы решения нелинейных уравнений83где S(x) = х - тВ 'F(x). Тем самым (6.12) соответствует применениюметода простой итерации для преобразованного уравнениях = S {х).(6.13)Пусть в окрестности R = {х | ||х - х°|| ^ г} заданного начальногоприближения х° выполнены условия| | S ( * ) - S ( y ) | | < « | | s - y | | , x,y€R,||x0-S(x°)||^(l-l)r,q<\.Тогда уравнение (6.13) имеет в R единственное решение х*, которое даетсяитерационным процессом (6.12), причем для погрешности справедливаоценка|х* + | - х*^Л°-х*В методе Ньютона новое приближение для решения системы уравнений (6.2) определяется из решения системы линейных уравнений+ /,(х*)=0,dXj(6.14)i = l , 2 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
