Главная » Просмотр файлов » Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений

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

Файл №947493 Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (Богачев - Практикум на ЭВМ) 16 страницаБогачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493) страница 162013-09-15СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 74 б) одно умножение, одно сложение и одна операция извлечения корня для вычисления ~~аь' )~~ в (10),: в) одно вычитание для построения вектора хьй) в (11): г) одно умножение, одно сложение и одна операция извлечения корня для вычисления !/х~й)// в (12); д) и — й делений для построения вектора хьй) в (13).

Всего для построения матрицы П(хй) требуется (и — й — 1)+1+1+ (и — й) = 2(п — й) + 1 мультипликативных, (и — й — 2) + 1 + 1 + 1 = п — й + 1 аддитивных операций и 1 + 1 = 2 операции извлечения корня. 2. Компоненты 1+1,..., и й-го столбца матрицы Аьй), равные компонентам ьй — ь) ьч — й) вектора ~)а~ ~(е~, уже вычислены в (10). Столбец й вычисляется не по общим формулам (7) для сокращения количества арифметических операций и уменыпения вычислительной погрешности. 3. Поскольку в формуле (7) матрица П(хй) Е М„й умножается на подматрицу (и)"; "))ь й.ь.ь „, й.ьь „матрицы Аьй ') размера (п — й) х (п — й) (й-й столбец матрицы Аьй) уже вычислен в пункте 2), то согласно лемме 13.11 на это требуется 2(п — й) + 0(п — й) (и -+ сс) умножений и столько же сложений.

4. Поскольку в формуле (8) матрица П(хй) е М„й умножается на подматрицу (а; ); — ь „,„,ь — й.ьь „матрицы А размера и х (п — й), то согласно ьй-ь) ьй — ь) лемме 13.11 на зто требуется 2(п — й)п+0(п — Й) (и -+ оо) умножений и столько же сложений. Итак, на й-ом шаге алгоритма требуется выполнить 2(п — й) + 1+ 2(ив й)~+ 2п(п — й) + 0(п — й) = 2п(п — й) + 2(п — й) + 0(п — й) мультипликативных операций, п — К+1+2(п — К)г+2п(п — И)+0(п — К) = 2п(п — )ь)+2(п — й) +0(п — й) адцитивных операций и 2 операции извлечения корня. Следовательно, всего для проведения алгоритма требуется выполнить и — 2 ~, (2п(п — й) + 2(п — й) + 0(п — й)) й=ь = 2п((п — 1)(п — 2)/2) + 2((п — 1)(п — 2)(2п — 3)/6) + 0(п ) = пг + 0(п ) + 2~из + 0(п ) = 5 из + 0(п ) (и — + оо) мультипликативных операций, столько же адцитивных операций и 2(п — 2) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления).

Таким образом,на приведение матрицы к почти треугольному виду унитарным подобием методом отРажений тРебУетсЯ ~зпг + 0(п~) (п -+ сс) мУльтипликативных операций и столько же аддитивных операций. Заметим, что это количество операций в два с половиной раза больше, чем нужно для решения линейной системы методом отражений. Теорема 1. Веякол невььрооьсденная матрица А моэьсет быть представлена в виде А = ЯВЯ~, где матрица Я вЂ” унитарная, а матрица  — верхнял почти треугольная. К.Ю.Богачев Точные методы решения линейных систем Доказательство. Проведем для матрицы А изложенный вьппе алгоритм, осуществимый для всякой невырожденной матрицы.

Обозначим в (14) » П П». Как произведение унитарных матриц, матрица Я унитарна. Тогда (14) »= — г имеет вид Н = ЯАф, откуда А = (ф»В(ф) ' = ЯВЯ', где Я = ®)' = ®) ' — унитарная матрица. Матрица В, имеющая вид (14.12), удовлетворяет условиям теоремы. Замечание 1. Как отмечалось вы»пе, построенное в теореме 1 разложение используется в ряде алгоритмов нахождения собственных значений матрицы.

Хранение матриц Я и В в памяти осуществляется одним из способов, изложенных при обсуждении алгоритма построения ЯР»-разложения для матрицы А методом отражений. Трудоемкость алгоритма построения описанного вьппе разложения складывается из количества арифметических операций, необходимых для проведения самого алгоритма, и количества арифметических операций, необходимых для построения матрицы Я. Подробные выкладки были проведены при обсуждении алгоритма построения ЯЛ-разложения методом отражений.

з 15.2. Случай самосопряженной матрицы Рассмотрим ситуацию, когда описанный выше метод приведения к почти треугольному виду применяется к самосопряженной матрице А е М„. Согласно (14.1), (14.2) А»»» = П»АП»', где Ь»» — унитарная матрица, т.е. А»»» и А — унитарно подобны. Следовательно, А»»~ — самосопряженная матрица. Согласно (7), (8) на й-ом (й = 1,..., и — 2) шаге алгоритма А® = 11~А»" »»Пъ», где Пь — унитарная матрица.

Следовательно, А~ъ~ и А унитарно подобны, и А~"~ — самосопряженная матрица для всякого й = 1,..., и — 2. Таким образом, В = А»" 㻠— почти треугольная н самосопряженная, т.е. трехдиагональная матрица. Запишем описанный выше процесс приведения самосопряженной матрицы к трехдиагональному виду так, чтобы максимально уменьшить объем вычислительной работы за счет использования симметрии. Лемма 1.

Для всякой матрицы оп»ражения П = с»(х) Е М„и всякой самосопряженной матрицы А Е Мъ матрица В = ПАП* = ПАП может быть вычислена за 2пг+ 0(п) умножений и столько же сложений. Доказательство. Поскольку Ь»(х) = 1 — 2хх", то В = (1 — 2хх*)А(1 — 2хх*) = (1 — 2хх*)(А — 2Ахх*) = А — 2Ахх* — 2хх*А+4хх*Ахх*. Обозначим (15) у = Ах Е С" К.Ю.Богачев Точные методы решения линейных систем ~1 О. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 75 В силу самосопряженности матрицы А имеем у = Ах = А*х = (х*А)*, 4хх'Ахх" = 2хх*Ахх* + 2хх'Ахх" = 2хх" ух* + 2ху'хх* В = А — 2ух' — 2ху'+ 2хх*ух* + 2ху*хх' = А — 2(1 — хх*)ух* — 2ху*(1 — хх") Обозначим я = 2(1 — хх*)у = 2у — х(х" у) = 2у — 2(х, у)х.

(16) Тогда В = А — ах* — хг* (17) После этих преобразований мы можем сформулировать алгоритм вычисления матрицы В: 1) Вычисляется вектор у по формуле (15). На это требуется па+ О(п) мультипликативных операций и столько же аддитивных операций. 2) Вычисляется вектор я по формуле (16). На вычисление а = 2(х, у) — удвоенного евклидова скалярного произведения, требуется и + О(1) мультипликативных операций и столько же андитивных операций; на вычисление я = 2у — ах требуется 2п мультипликативных операций и п аддитивных операций. Общее число операция, необходимое для вычисления вектора я Зп+ 0(1) мультипликативных и 2п + 0(1) а,пдитивных операций. 3) Вычисляется матрица В по формуле (17).

Матрица В как унитарно подобная А самосопряжена, поэтому по формуле (17) вычисляются только п(и+ 1)/2 элементов верхнего треугольника матрицы В. На вычисление каждого элемента матрицы В по формуле (17) надо выполнить 2 умножения и 2 вычитания, поэтому трудоемкость вычисления В по формуле (17) равна п(п+ 1) = и + 0(п) мультипликативным и п~ + 0(п) аддитивным операциям. Таким образом, этот алгоритм требует и +0(п)+Зп+0(1)+и +0(п) = 2п + 0(п) мультипликативных и столько же аддитивных операций.

Лемма доказана. Замечание 2. Для несамосопряженной матрицы А вычисление матрицы В = 17АП требует 4п + О(и) умножений столько же сложений (см. лемму 13.11). Обозначим а1 — — (а~1,..., а,п) . Согласно лемме 13.9 существует вектор х (0 С", равный 60 а1 — !)аг (/е1 !)а1 — ))а1 (/е1 )/ такой, что П(х0~)а1 = Д~а1Де1, где е1 — — (1,0,...,О) Е С" ', П(х~0) б М„1 — матрица отражения. Введем матрицу П1 как в (2) и вычислим матрицу К.Ю.Богачев Точные методы ретения линейных систем 315.

ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 76 АО) = П1АП1. В силу самосопряженности матрицы АО) вместо (14.2) для нее справедливо более точное равенство а11 )(а1!) 0 ... О ~!п1~! пгг пгз пг (Ц (Ц 00 (Ц (Ц (Ц пзг пзз пз АО) = П1АП1 —— (18) 0 а„г а„з ... а„„ 10 11) (Ц Таким образом, у матрицы АО) необходимо с помощью леммы 1 вычислить только подматрицу (а;1 );, — г „Е М„1 (так как остальные элементы уже вы- (Ц числены) . Пусть сделаны Й вЂ” 1, Й = 1,...,п — 1 шагов этого процесса, т.е.

матрица преобразована к виду (14.3), где матрица А1й ') имеет вид (14.14). Введем обозначение (14.5). Согласно лемме 13.9 существует матрица отражения (4) такая, что выполнено (5). Определим Пй равенством (6). Вычислим матрицу А1~) = 17йА1" ')с1й. (19) Матрица А1й) унитарно подобна самосопряженной матрице А1й 1). Поэтому она самосопряжена и вместо (14.10) для нее справедливо более точное равенство (14.16). Таким образом, у матрицы А1й) необходимо с помощью леммы 1 вычислить только подматрицу (а; );, й„1 „Е М„й 1 (так как остальные эле(й) менты уже вычислены).

После и — 2 пгагов этого процесса (т.е. перехода от матриц (14.3), (14.14) к (19), (14.16)) матрица примет требуемый трехциагональный вид (14.17). Оценка количества арифметических операций в алгоритме приведения самосопряженной матрицы к трехдиагональному виду унитарным подобием методом отражений Оценим трудоемкость к-го шага алгоритма, а затем просуммируем полученные оценки по всем й = 1,..., п — 2. 1. На вычисление матрицы П(хй) по формулам (4) требуется 2(п — Й) + 1 мультипликативных, п — 1+ 1 аддитивных операций и 2 операции извлечения корня (см. вычисления при оценке количества арифметических операций в алгоритме приведения матрицы к почти треугольному виду унитарным подобием методом отражений). 2.

Характеристики

Тип файла
DJVU-файл
Размер
497,22 Kb
Тип материала
Учебное заведение
Неизвестно

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6511
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее