Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (Богачев - Практикум на ЭВМ), страница 9

Поэтому (й — Ц (й) (й-1) из формул (5) получаем, что вектор е; получается из вектора е; изменением не более чем первых й компонент. По предположению у вектора е; (й — 1) возможно отличны от нуля только компоненты 1,..., й — 1 и г. Следовательно, у е;, г = )с + 1,...,п могут быть отличны от нуля компоненты с номерами (й) 1,..., Й и г.

Следствие 1. По доказанному в лемме 1 вектор е( получается из е( из(й) (й) менением компонент 1,..., Й (остальные компоненты у вектора ей нулевые). (й — 1) Следовательно, у всех е„й, Й = 1,..., и (и+1)-я компонента равна 1. Поэтому вектор е„11 является решением задачи (4). (и) Оценка количества арифметических операций в методе ортогонализации Оценим трудоемкость вычислений по формулам (5) для фиксированного /с, а затем просуммируем полученные оценки по всем Й = 1,..., и. 1.

Знаменатель (Ай,ей ) в (5) от г не зависит и вычисляется один раз (й — 1) (й — 1) для каждого й. В силу леммы 1 у вектора ей только компоненты 1,..., й могут быть отличны от нуля, поэтому на вычисление скалярного произведения (Ай, ей ) потребуется й операций умножения и й — 1 операций сложения. (й-1) (й-1) 2. На вычисление скалярного произведения (Ай, е; ) в (5) по лемме 1 потребуется й операций умножения и й — 1 операций сложения (поскольку у вектора е1 только компоненты 1,..., й — 1 и 1 могут быть отличны от нуля). Следова(й — 1) тельно, на вычисление этих скалярных произведений для всех г = 1+1,..., и потребуется ~," й, й = й(п — й) операций умножения и 2 ' й11(й — 1) = (й — 1)(п — й) операций сложения.

(Ай,е(й ')) 3. Навычислениедроби ' '„, длявсех г = 1+1,...,п в(5) потребуется (Ай, ей ) и — Й операций деления. 4. На вычисление вектора е( по формуле (5) при условии, что дробь (й) (А,, е('-')) уже вычислена, потребуется Й операций умножения и столько же (Ай, е( )) (й — 1) операций сложения (поскольку в силу леммы 1 у вектора ей только компоненты 1,..., й могут быть отличны от нуля). Следовательно, на проведение этих вычислений для всех г = й+ 1,..., и потребуется ~," й, й = й(п — й) операций умножения и столько же операций сложения. Итак, при фиксированном Й = 1,..., п трудоемкость формул (5) составляет й + й(п — й) + (и — й) + й(п — й) = 2й(п — й) + и мультипликативных операций и Й вЂ” 1+ (/с — 1)(п — Й) + Й(п — Й) = 2Й(п — Й) + 2Й вЂ” и — 1 аддитивных операций.

Следовательно, трудоемкость всего метода ортогонализации составляет К.Ю.Богачев Точные методы решения линейных систем '3П. МЕТОД ОРТОГОНАЛИЗАЦИИ 42 '1 „",(Ы(п — Й) + и) = 2п ~ „", Й вЂ” 2 ~„~, к~+ и = 2и п(п+ 1)/2 — 2п(п+ 1) (2п+ 1)/6+ аз = из+ О(пз) — ~~пз+ О(п') = па/3+ О(п~) мультипликативных операций и 2 ~,(2Й(п — й)+21 — п — 1) = пз/3+О(п~) аддитивных операций.

Таким образом, метод ортогонализации асимптотически требует такого же количества арифметических операций (суммарно 2 па+ О(п ) (и -э оо) ), как и метод Гаусса. МЕТОДЫ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ> ОСНОВАННЫЕ НА УНИТАРНЫХ ПРЕОБРАЗОВАНИЯХ МАТРИЦ Каждый из изложенных выше методов решения линейных систем может быть представлен в виде последовательности элементарных преобразований матрицы (см., например, такое представление в 34 для метода Гаусса). Каждое из преобразований задается некоторой матрицей Р, так что применение этого преобразования эквивалентно умножению (слева) исходной матрицы А на матрицу Р. Таким образом, каждый шаг приведенных вьппе алгоритмов есть переход от матрицы А к матрице А:= РА.

О числе обусловленности этой новой матрицы А:= РА можно лишь утверждать, что к(РА) < к(Р)к(А). Поэтому может случиться так, что в процессе проведения преобразований число обусловленности матрицы возрастает и на каждом шаге метод будет вносить все болыпую вычислительную погрешность. В результате может оказаться,что исходная матрица имела приемлемое число обусловленности, однако после нескольких шагов алгоритма она уже имеет слишком большое число обусловленности, так что последующие шаги алгоритма приведут к появлению очень большой вычислительной погрешности. Возникает идея подбирать матрицы преобразования Р так, чтобы число обусловленности матрицы в процессе преобразований не возрастало. Лемма 1.5 указывает нам пример таких матриц: если матрица преобразования Р унитарна (ортогональна в вещественном случае), то относительно спектральной нормы к(РА) = к(А).

Излагаемые ниже метод вращений и метод отражений представляют собой алгоритмы подбора унитарных матриц преобразований Р, таких, что в результате всех этих преобразований исходная матрица А приводится к треугольному виду. Система с треугольной матрицей затем решается, например, обратным ходом метода Гаусса. Несмотря на то, что трудоемкость этих методов больше, чем метода Гаусса (соответственно в 3 и 2 раза), эти методы получили широкое распостранение в вычислительной практике благодаря своей устойчивости к накоплению вычислительной погрептности.

К.Ю.Богачев Точные методы решения линейных систем ~12. МЕТОД ИЧЩЕНИИ 43 0 12. МЕТОД ВРАЩЕНИЙ В этом методе в качестве элементарного преобразования матрицы выбирается умножение ее на матрицу вращения. Э 12.1. Матрица элементарного вращения и ее свойства Определение. Элементарным вращением Т;, = Т;,(у) называется преобразование пространства, задаваемое матрицей Т;, = (1н)ь ~ т „, в которой только следующие элементы отличны от нуля: Ц; = сову, 10 = сову, 1;, = — япу, 1эт = яп у, 1ц, = 1 для всех Й = 1,..., и, Й ~ г', у: — япу сову япу Если (еь..., е„) -- базис С" ( еь — — (О,...,О, 1,0,..., 0)'), то Т,: является й — 1 вращением в подпространстве (е,, е ) и не изменяет подпространства (еп...,е, т,е;+и...,еэ пеу+ь...,е„) (другими словами, Т,', изменяет только 1- ю и у-ю координаты векторов).

Поэтому для изучения свойств преобразования Т; достаточно изучить свойства преобразования т= ("'у ~ яву сову / в двумерном пространстве. Лемма 1. Матприца Т; являетпсл ортогональной матрицей. Доказательство. Следует из ортогональности матрицы Т. /х1 Лемма 2. Длл всякого вектора г = ~ ) е 1ьг, г ф 0 сущестует матриу /сову — япу 1 (й ,.т=(. ), -, ° т,=~~в(),и.~~п=„и+р— ~ яву сову ) ' 10) ' евклидова длина вектора г. При этом трудоемкость постпроенил матприцы Т составляетп 4 мультипликативные операции, одну аддитивную и одну операцию иэвлеченил корня.

К.Ю.Богачев Точные методы ретевия линейных систем ~12. МЕТОД ШПЩЕНИИ Доказательство. Достаточно положить х у СОЗЕ = яп)р =— х + у ' х/хт+у2' Лемма 3. Для всякого векпгора х ~ К", х ~ О сущестуют и — 1 матриц Т)2 = Тгг(1р)г), Т)з = Т1з(1р1з),, Т)п = Т)„(1р1„), таких, что Т)„... ТгзТггх = ))х)) е1, где ))х)) = ))х))2 = 1 ~ х~~ - евклидова длина вектора х, е1 — — (1,О,...,О)' '~ и=1 -- первый координапгный орт. Доказательство. Если вектор г = ф О, то по лемме 2 существует 1' х) '1 ),Х2 ~ матрица элементарного вра)цения СОЯ ф12 — ВП1 ф12 ЯП1 Р)2 СОЯ 'Р12 / (й такая, что Тг = ~~г~( ~ (.

Тогда матрица сов:Р12 — Яп ~Р12 Яп )Р12 сов 1Р12 Т12 = Т12(ф12) = ° г ~~ «* р «р "'=г.*=)/Г4,0,,", .)' з «р 1Х1'1 г = = О, то преобразование не осуществляется (Тгг — — 1 - единичной Х2 матрипе). После Й вЂ” 1 щагов этого процесса (Й = 1,..., и — 1) вектор х преобразован к ° ч~ ()=т, .г„*=))с1, )о,...,в, а,,...,*,)'.к «*Р г = ~-~=1 хз ~ 1~2, г ~ О, ХЗ-)-1 то по лемме 2 существует матрица элементарного вращения 1 сов )Р),ц1.1 — Яп 1Р),~).1 т=т(р,,„„,)= ~ . '1 яп)р),ь).1 сов 1р),~„1 К.Ю.Богачев Точные методы ретения линейных систем ~12. МЕТОД БРАЩЕНИИ 45 (1'1 такая, что Тг = ~(г~( ) .

Тогда матрица — ейп ~рця+1 сов уця+1 Т, я+, — Т, я+, (~Р, я+,) = з1п Фця-н сов уць+1 1 переводит вектор х~"~ в вектор я-~-1 х =Т1я+1х =Т1я+1Тгя...Т12х= ( ~ х,0,...,0,хя+г,...,х ) и=г Если вектор г = О, то преобразование не осуществляется (Т1 я+1 — — 1 — единичной матрице).

После и — 1 шагов этого процесса вектор х будет преобразован к виду х~"~ = г,„...т„,= ( гс, фо,...,ог= ь~$., Лемма 4. Произведение матрицы элементарного вращения на вектор можегп быть вычислено за 4 умноженил и 2 сложения. Доказательство. Произведение у = Т,: (у;-)х матрицы элементарного вращения Т; на вектор х имеет следующие компоненты: Уь =хя~ Й = 1,...,н, й ф2,У, У~ = хгсозф~э — х181пЩ, Уэ =х~зш~оц+хусозЦ)Е'. При осуществлении вычислений по этим формулам надо выполнить 4 умноже- ния и 2 сложения. Замечание 1.

Для вычисления произведения матрицы из М„общего вида на вектор требуется выполнить н~ умножений и н(н — 1) сложений. Доказательство. Пусть н х т матрица У = Т; Х есть произведение матрицы элементарного вращения Т; е М„на н х т матрицу Х. Запишем матрицы Х = (х; ) и У = (у; ) через их столбцы: Х = [х~Ц,..., х~"ч1, У = ~у~Ц,..., у~'"~~, К.Ю.Богачев Точные методы решения линейных систем Лемма 5.

Произведение матрицы элементарного вращения Т;, Е М„на магарицу размера и х т может быть вычислено за 4т умножений и 2т сложений. ~12. МКТОД ИПЩКНИй 46 где х1") = (х1ю...,х„ь)', у1") = (у1ю..., у„~)1, Й = 1,...,т. Согласно определению произведения матриц У = Т,' Х = (Т,: х1'),..., 7;:ух1'"")], те. у1"~ = Т; х1"), й = 1,..., га. Таким образом, для вычисления матрицы У = Т;,Х надо вычислить т произведений Т,: х1") матрицы Т; на вектора х1"), й = 1,..., ш. Доказываемое утверждение теперь вытекает из леммы 4. Замечание 2. Для вычисления произведения двух матриц из М„общего вида требуется выполнить пз умножений и пз(п — 1) сложений. 3 12.2.