А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (2000) (1160081), страница 5
Текст из файла (страница 5)
Алгоритмы решения систем линейных уравнений39Разложение (3.4) и решение системы (3.5) связывается с прямым ходомв методе исключения неизвестных, а решение системы (3.6) — с обратнымходом.В методе Гаусса с выбором главного элемента на очередном шагеисключается неизвестное, коэффициент по модулю при котором является наибольшим. В этом случае метод Гаусса применим для любыхневырожденных матриц А, т.
е. матриц, для которых det(j4) Ф 0.Матрицей перестановок Р называется квадратная матрица, у которойв каждой строке и в каждом столбце только один элемент отличен от нуляи равен единице. При det (А) Ф 0 существует матрица перестановок Ртакая, что справедливо разложениеРА = LU.Тем самым метод Гаусса с выбором главного элемента соответствуетприменению обычного метода Гаусса, который применяется к системе,полученной из исходной системы перестановкой некоторых уравнений.3.2.3. Метод квадратного корняПри решении системы уравнений (3.1) с симметричной вещественнойневырожденной матрицей А используется разложениеА = S*DS,где S — верхняя треугольная матрица с положительными элементамина главной диагонали, 5* — транспонированная к ней (s*t] = з]г), a D —диагональная матрица с элементами d,, i = 1,2,...,п, равными ±1.Вычисления на основе этого разложения определяют метод квадратногокорня (метод Холецкого).Для элементов матриц S и D используются расчетные формулы:d, = sign а п ,an = | а п | , / 2 ,d, = signf o„ - Y^ M2d* ).t=i^I»-'*n = UII - ]Tj«*tl 2 d*'11/2.sl} = - ^ ,j = 2,3,...,n,Глава 3.
Прямые методы линейной алгебры40» = 2,3,...,n,j = t + l,i + 2,...,n.В методе квадратного корня вычислительные затраты примерно в двараза меньше, чем в стандартном методе Гаусса (эффект учета симметрииматрицы задачи).3.3. УпражненияЗдесь рассматриваются основные характеристики квадратных вещественных матриц, свойств прямых методов решения систем линейных уравнений, базирующихся на треугольном разложении матрицы системы.Упражнение 3.1.
Показать, что норма матрицып114.= ™*, 51 К!'•- J ~"1=1подчинена норме вектора1И1, = 5 > | .i=iРешение Для произвольного вектора х имеемАхм711=1J=l\\} = ^2^2ачх1 ^ S ] C w * j i <J=I1=1 j = i1=1^ ° ^ n 1=1'Поэтому достаточно показать, что существует вектор я, для которогов последнем неравенстве достигается равенство. Пустьляmax ] Г | а , ; | = ]Г>'*1'3.3. Упражнения41тогда можно взять вектор х с компонентами х, = 0, i ф к, х* = 1. Темсамым норма матрицы Ц-АЦ, подчинена норме вектора ||х||,.Упражнение 3.2. Покажите, чтоcond (А) > £ = £ g J(3.7)|Amin (А) |Решение.
Для собственного вектора v, отвечающего наибольшему по модулю собственному значению, имеем равенствоAv = Amaxv.В силу этого11-4*11 = |Amaxl ||*||,что, принимая во внимание \\Av\\ ^ \\А\\ ||г»||, дает неравенство\\А\\ > |А тах |.(3.8)Для обратной матрицы А'1 максимальным по модулю являетсясобственное значение А^.'п и поэтому\\А-'\\^\Хтп\-\(3.9)Из (3.9) и (3.8) следует доказываемое неравенство (3.7).Упражнение 3.3. Приведите расчетные формулы метода Гаусса для решениясистемы уравнений с трехдиагональной матрицей.Решение.
На основе обших расчетных формул компактной схемы методаГаусса для матриц L и {/ получим.«21И||=ац,Ui2 = ai2,«21 = — ,«it = a.i-'.,i-iM»-i,:,Wi,i+i =«I,I+i)h+\,% =«пS t = 2,3,...,n.Эти формулы приводят к следующему рекуррентному соотношению дляэлементов матрицы L:42Глава 3. Прямые методы линейной алгебрыРеализация (3.5) в нашем случае даетУ\ = / i ,»i = / » - ' t , . - i y » - i ,t = 2,3,...,n.А из (3.6) находится решение системы уравнений:УпХп —°mn'n,n-l<ln-l,nX, = - ^ ^ ( j / , - a, t , + i X , + i ) ,a«+l,i1 = П - 1 , 7 1 - 2 , . . . , 1.Приведенные формулы могут рассматриваться как один из вариантовалгоритма прогонки.Упражнение 3.4.
Постройте алгоритм обращения квадратной матрицына основе использования метода Гаусса.Решение. Нахождение матрицы А~х эквивалентно решению матричногоуравненияАХ = Е,(3.10)где X — искомая квадратная матрица. Перепишем уравнение (3.10) в видесистемы п2 уравнений для нахождения элементов ху, i,j = 1,2,...,пматрицы X:п]Га,*х*_, = <>,;,i,j = l , 2 , .
. . , n ,(3.11)где 6Х] — символ Кронекера:Ч": ПСистема уравнений (3.11) в силу отмеченной специфики правойчасти распадается на п независимых систем уравнений с одной и той жематрицей А и различными правыми частями. Определим вектора* W = {*„},е<»> = {*,},,'=1,2,...,пи перейдем к п системам уравнений:Л* 0 ) = е 0 ) ,j = 1,2,...,».433.3. УпражненияПосле треугольного разложения (3.4) матрицы А решаются уравненияс треугольными матрицами:Ьуи)=еЬ),С/ж ы =г/°\j = 1,2,..., п.Упражнение 3.5. Подсчитайте число арифметических действий при решенисистемы уравнений методом квадратного корня.Решение. Ограничимся случаем положительно определенной симметричной вещественной матрицы ((Ах,х) > О, А = А*). В этом случае треугольное разложение имеет вид А = S*S, причем« п = (an)=/, *ij = — ,«и«« --1'a2( »-]O*«) ) '*=1*=i^.,- V'• -11 /*"'1/21/2ч\si = 2,3,...,n,*=1г = 2,3, ..,n, j = i + l,i + 2,...,n.Вычисления диагональных элементов требуютумножений.
Для каждого фиксированного j для вычисления внедиагональных элементов требуется«=2умножений, а всегоАО'-1Щ-2) = п(п-1)(п-2)J=2умножений. Число делений совпадает с число внедиагональных элементовматрицы S и поэтому для реализации треугольного разложения требуетсяп(п- 1)(п + 4)6п3644Глава 3. Прямые методы линейной алгебрыДля нахождения решения системы уравнений (3.1) после треугольного разложения решаются две системы уравненийSx = у,S*y = /,что требует еще п(п + 1) операций умножения и деления. Аналогичноподсчитывается число сложений.Упражнение З.б. ПустьA = S*S> 0.Выразите число обусловленности матрицы А через число обусловленностиматрицы S.Решение.
Для симметричной положительно определенной вещественнойматрицы А норма определяется выражениемIN II-nn^'iwi'-S («,«)'С учетом этогоcond(A) = | | A | | 2 | | ^ - ' | | 2 = sup(x, Ax)x,A 'a;)s u p 0(x,x) хфй (x,x)(Sx, Sx)(5--]x,S~l x)= sup — sup —in1(Г11*1*-•ieи поэтому cond (A) = (cond(S)) .3.4. ЗадачиЗадача 3.1. Доказать следующие неравенства для норм векторов:NL<IN,<»INL.^IN,<IHl2<N,.NL^NU^INL.3.4. Задачи45Задача 3.2. Покажите, что норма матрицы\\А\\2=у/^А)(через д(А) обозначен спектральный радиус матрицы А — максимальноепо модулю собственное значение матрицы) подчинена норме вектора2 1/2= (i>i )Задача 3.3. Покажите, что норма матрицыпз=\является подчиненной норме вектораllxll11 |1о= max \xA.°|<|^п' 'Задача 3.4. Покажите справедливость следующих неравенств для нормматриц:ilHL<IHI,<»IWLЗадача 3.5.
М-норма квадратной матрицы А определяется выражениемМ(А) = п max |(ц,-|.Покажите справедливость неравенств^М(А)^\\А\\оо^М(А),-М(А)^\\А\\^М(А),п-М(А)^\\А\\2КЩА).Глава 3. Прямые методы линейной алгебры46Задача 3.6. Доказать неравенствоЗадача 3.7. Покажите, что для собственных значений симметричнойматрицы А справедливы оценки> max а.ц, Amin < min ац.Задача 3.8. Покажите, что для 1-, 2-, оо-норм матрицы число обусловленности не меняется при перестановке строк и столбцов.Задача 3.9.
Показать, что для п хп матрицы имеет место неравенство1condoc(^) ^~ ^7ТТГ ^ п-Задача 3.10. Вещественная матрица А называется ортогональной, еслисопряженная матрица А* совпадает с обратной А'1. Докажите, чтодля cond (А) — 1, если А — ортогональная матрица.Задача 3.11. Пусть А — матрица со строгим диагональным преобладанием по строкам (по столбцам), т. е.|a»l>5Zl a ijl[M>^2\aji\J,*=l,2,...,n.Докажите, что в этом случае матрица А невырожденная.Задача 3.12. Пусть вещественная матрица А симметричная и положительно определена (А = А* > 0). Докажите, чтоD = diag{o,,,a 2 2 ,...,a n n } > 0.Задача 3.13. Докажите, что, если А — симметричная и положительноопределенная матрица, то max|a,j| достигается при г = j .ij3.4. Задачи47Задача 3.14.
Пусть А — матрица с элементамива» > 5Z К>1> а 0 < °> если * ^•?' * = ] > 2 > • • • ."•Покажите, что матрица .4"' имеет только положительные элементы.Задача 3.15. Подсчитайте число арифметических действий при решениисистемы линейных уравнений методом Гаусса.Задача 3.16. Получите расчетные формулы для определителя симметричной вещественной матрицы на основе использования разложенияХолецкого.Глава 4Итерационные методылинейной алгебрыДля приближенного решения больших систем линейных алгебраических уравнений используются итерационные методы.
Такиесистемы возникают при приближенном решении многомерныхкраевых задач математической физики. Рассмотрение начинается с классических итерационных методов Якоби и Зейделя.Приведены базовые понятия теории итерационных методов решения систем линейных уравнений, рассматриваемых в евклидовых пространствах. Обсуждаются проблемы выбора итерационныхпараметров, выбора матрицы перехода (переобуславливателя).4.1. Итерационное решениесистем линейных уравненийРассматриваются проблемы итерационного решения системы линейныхуравненийАх = f(4.1)для нахождения вектора х. В теории итерационных методов матрица А,обычно, рассматривается как линейный оператор, действующий в евклидовом пространстве Н = 12, в котором скалярное произведение есть(я,У) = Ylx,yi'aн°Р м а INI = (Х,ХУ/2-!=1Итерационный метод основан на том, что начиная с некоторогоначального приближения х° G Н последовательно определяются приближенные решения уравнения (4.1) х\х2,...,хк,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
