WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     || 2 | 3 | 4 | 5 |

«ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ АЛГЕБРЫ И ОЦЕНИВАНИЯ 1 2i 0 2 0 x2 i 2 1 + i = 1 1 i+1 4 2 = 2i 1 ) ) 1 2 2( i + 2 + i( 0 = 0 i+1 x1 0 4 Ульяновск 2011 министерство образования и науки российской федерации федеральное ...»

-- [ Страница 1 ] --

И. В. Семушин

ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ

АЛГЕБРЫ И ОЦЕНИВАНИЯ

1

2i

0 2 0

x2

i 2 1

+

i

=

1 1 i+1 4 2 = 2i 1 ) ) 1 2 2( i + + i( = i+1 x 0 Ульяновск министерство образования и науки российской федерации федеральное государственное бюджетное образовательное учреждение высшего профессионального образования ульяновский государственный технический университет И. В. Семушин

ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ

АЛГЕБРЫ И ОЦЕНИВАНИЯ

Учебное пособие Ульяновск УлГТУ УДК 519.61 + 519.654 + 519.244. ББК 22.193я С Рецензенты: Профессор д-р Б. С. Верховский, Кафедра ВТ, Заслуженный деятель науки РФ, кафедра математики, Пензенская государственная технологическая академия Рецензия кафедры общей информатики, Самарский государственный аэрокосмический университет им. акад. С. П. Королёва. Заведующий кафедрой профессор, д-р техн. наук В. А. Фурсов Утверждено редакционно-издательским советом университета С30 Вычислительные методы алгебры и оценивания : учебное пособие / И. В. Семушин. Ульяновск : УлГТУ, 2011. 366 c.

ISBN 978-5-9795-0902- Книга сообщает базовые сведения по вычислительной линейной алгебре и линейному оцениванию. Знакомит с эффективными алгоритмами дискретной фильтрации. Включает контрольные задачи и лабораторные проекты с большим числом индивидуальных заданий.

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

ISBN 978-5-9795-0902- russian federation’s ministry for education and science Federal State Budget Educational Institution for ulyanovsk state technical university

COMPUTATIONAL METHODS OF

ALGEBRA AND ESTIMATION

UDC 519.61 + 519.654 + 519.244. BBK 22.193я Reviewers: Professor Dr. Boris S. Verkhovsky, CS Department, Professor Dr. Vitaly I. Levin, RF’s Honoured Science Worker, Math Department, Penza State Academy of Technology Department of Basic Informatics, Academician S. P. Korolyov Samara State Aerospace University submitted its approval of the book. Signed by Professor Dr. Vladimir A. Fursov, Head of Department С30 Computational Methods of Algebra and Estimation : textbook / I. V. Semushin. Ulyanovsk : UlSTU, 2011. 366 c.

ISBN 978-5-9795-0902- The book conveys the basic knowledge in Computational Linear Algebra and Linear Estimation. It familiarizes with the ecient algorithms of discrete ltering, and includes test problems and laboratory projects with the great number of individual assignments.

For students who learn Numerical Methods as a discipline of study at the bachelor degree or diploma level as well as for PhD students and specialists in the eld of Mathematical Modeling, Numerical Methods and Integtated Software.

ISBN 978-5-9795-0902- For the things we have to learn before we can do them, Ибо то, что нам надо постичь, чтобы уметь это делать, Оглавление Стандартные алгоритмы LU -разложения.......

3 Векторно-ориентированные алгоритмы LU разложения............................

ОГЛАВЛЕНИЕ

Алгоритмы окаймления в LU -разложении......

4.2 Окаймление известной части разложения......... 4.3 Окаймление неизвестной части разложения........ 4.5 Варианты задания на лабораторный проект № 3..... Разреженные формы LU -разложения..........

5.4 Варианты задания на лабораторный проект № 4..... 6.2 Квадратные корни из P и алгоритмы Холесского..... 6.3 Программная реализация алгоритмов Холесского..... 6.4 Разложение Холесского: ijk-формы............. 6.5 Разложение Холесского: алгоритмы окаймления..... 6.8 Варианты задания на лабораторный проект № 5..... 7 Ортогональные преобразования.............. 7.1 Ортогональные матрицы и приложения.......... 7.2 Линейная задача наименьших квадратов.......... 7.3 Ортогональные матрицы и наименьшие квадраты.... 7.4 Преобразование Хаусхолдера................ 7.5 Шаг триангуляризации матрицы методом Хаусхолдера. 7.6 Решение треугольной системы и обращение матриц... 7.8 Варианты заполнения матрицы R.............. 7.9 Правосторонние ортогональные преобразования..... 7.10 Двусторонние ортогональные преобразования....... 7.11 Ортогонализация Грама–Шмидта.............. 7.12 Алгоритмы ортогонализации Грама–Шмидта....... 7.13 Решение систем после ортогонализации.......... 7.14 Обращение матриц после ортогонализации........

ОГЛАВЛЕНИЕ

7.15 Задание на лабораторный проект № 6........... 7.16 Варианты задания на лабораторный проект № 6..... 8.5 Матричная запись методов Якоби и Зейделя....... 8.6 Каноническая форма одношаговых ИМ.......... 8.7 Методы простой итерации, Ричардсона и Юнга...... 8.8 Сходимость итерационных методов............. 8.9 Скорость сходимости итерационных методов....... 8.10 Итерационные методы вариационного типа........ 8.12 Задание на лабораторный проект № 7............ 8.13 Варианты задания на лабораторный проект № 7..... 9.2 Решения и рекомендации к типовым задачам....... 9.3 Варианты контрольных заданий.............. 9.4 Задачи для контрольных заданий и экзамена....... 10.1 Конечномерные линейные пространства.......... 10.2 Обобщение на гильбертовы пространства......... 10.3 Проектирование в конечномерных пространствах..... 10.4 Наименьшие квадраты и псевдоинверсия......... 10.5 Отыскание псевдообратной матрицы............ 10.6 Основные теоремы по МНК и псевдоинверсии...... 10.7 Вычисление матриц проектирования............ 10.9 Основные свойства симметрических / эрмитовых матриц

ОГЛАВЛЕНИЕ



11 Оценивание по методу наименьших квадратов... 11.1 Модели, регрессии и оценки................ 11.2 Линейная задача наименьших квадратов......... 11.3 Статистическая интерпретация............... 11.4 Включение априорных статистических данных...... 11.5 Включение предшествующего МНК-решения....... 11.6 Рекурсия МНК в стандартной информационной форме. 11.7 Рекурсия МНК в стандартной ковариационной форме. 11.8 Ковариационный алгоритм Поттера для МНК...... 11.9 Полная статистическая интерпретация рекурсии в МНК. 12 Одновременное решение нормальных уравнений.. 12.1 Метод нормальных уравнений................ 12.3 Задание на лабораторный проект № 8............ 12.4 Варианты задания на лабораторный проект № 8..... 13 Устойчивые алгоритмы фильтрации........... 13.1 Фильтрация Калмана в историческом аспекте....... 13.2 Стандартный фильтр Калмана............... 13.3 Скаляризованная форма фильтра Калмана........ 13.4 Стабилизованный фильтр Калмана–Джозефа....... 13.5 Квадратно-корневой фильтр Поттера........... 13.6 Одноранговое обновление ПО-матриц........... 13.7 Факторизованный фильтр Бирмана............. 13.8 Квадратно-корневой фильтр Карлсона........... 13.9 Редуцированный фильтр Бирмана............. 13.10 Редуцированный фильтр Бар-Ицхака........... 13.11 Редуцированный фильтр Бар-Ицхака–Медана....... 13.12 Задача сопровождения судна на траектории........ 13.13 Пример задачи с мультиколлинеарностью......... 13.14 Задание на лабораторный проект № 9............ 13.15 Варианты задания на лабораторный проект № 9..... 14 Ортогонализованные блочные алгоритмы....... 14.2 Блочные алгоритмы в исторической перспективе.....

ОГЛАВЛЕНИЕ

14.9 Скаляризованный модифицированный квадратнокорневой И-фильтр...................... 14.10 Скаляризованный комбинированный квадратнокорневой фильтр....................... 14.12 Варианты задания на лабораторный проект № 10..... A Обоснования алгоритмов для подразд. 14.7–14.10..... A.1 Построение новых скаляризованных алгоритмов..... B.3 Двойственность задач фильтрации и управления..... B.4 Вычислительные алгоритмы задачи управления..... Библиографический список...................... Предисловие Кафедра Информационные системы УлГТУ решением от 01.12..2011 г.

№ 12, рекомендует данное учебное пособие для студентов высших учебных заведений, обучающихся по направлениям:

230700.62 Прикладная информатика профиль Прикладная информатика в экономике, 231000.62 Программная инженерия, 230700.68 Прикладная информатика, 231000.68 Программная инженерия, а также для аспирантов по специальности 05.13.18 Математическое моделирование, численные методы и комплексы программ.

Кроме отмеченных, данное пособие может быть рекомендовано студентам и других направлений и специальностей, например, 010101 Математика при изучении дисциплины Методы вычислений, 010501 Прикладная математика и информатика при изучении дисциплины Численные методы, 010503 Математическое обеспечение и администрирование информационных систем при изучении дисциплины Вычислительная математика, 210400 Телекоммуникации при изучении дисциплины Вычислительная математика, 230200 Информационные системы при изучении дисциплины Вычислительная математика.

Несмотря на различия в названиях учебных дисциплин, курс Численные методы по многим специальностям и направлениям подготовки в университетах преследует следующие общие цели:

Предисловие заложить базовые умения и навыки в области разработки вычислительных алгоритмов решения задач, возникающих в процессе математического моделирования законов реального мира;

обеспечить понимание основных идей численных методов, особенностей и условий их применения;

подготовить студентов к применению этих знаний в дальнейшей учебе и практической деятельности.

При изучении данного курса значительное время отводят на Вычислительные методы алгебры, или Численные методы – I. Согласно требованиям Государственного образовательного стандарта [7], к фундаментальной части численных методов относят следующие темы из Вычислительной линейной алгебры (ВЛА):

тема 1 – методы исключения в решении систем;

тема 2 – разложения Холесского положительно определенных матриц;

тема 3 – методы ортогональных преобразований;

тема 4 – итерационные методы решения систем;

тема 5 – методы решения проблемы собственных значений матриц.

Часть I данного учебного пособия составили первые четыре темы из этого списка. Обширная тема 5, хотя и не включена, подготавливается здесь более основательным, чем обычно, изложением темы 3.

К ВЛА иногда относят тему Линейное программирование (ЛП), но чаще ее изучают как самостоятельный предмет, базирующийся на ВЛА, или включают ее в первый раздел таких дисциплин как Методы оптимальных решений или Исследование операций. Поэтому тема ЛП в данное пособие не вошла, по ней существует обширная литература, в частности, специальный компьютерный курс [76].

Часть II данного учебного пособия определена необходимостью изучения важной прикладной темы метода наименьших квадратов (МНК). В статистической интерпретации МНК означает оценивание неизвестных параметров математической модели (идентификация) или неизвестного состояния системы (фильтрация и предсказание). При том, что пособие предлагает по этой теме необходимый теоретический материал, основное внимание оно уделяет все же практической реализации методов оценивания. Благодаря включению в данное пособие этой части, названной Линейное оценивание, оно поддерживает изучение других прикладных дисциплин, таких как Прикладная статистика, Эконометрика или Стохастические модели, оценки и управление.

Понимание вопросов реализации методов оценивания, бесспорно, является решающим в приложениях теории. Однако, разработкам и исследованию численно устойчивых методов оценивания в отечественной научной литературе не уделено необходимое внимание. Еще меньшее внимание этому уделено в нашей учебной литературе, хотя численная неустойчивость теоретических методов оценивания существует как серьезный барьер для их практического применения. Акцентом на эффективную вычислительную реализацию методов оценивания в этом учебном пособии мы восполняем отмеченный пробел.

Учебная направленность всего предлагаемого материала выражена в том, что почти по каждой теме он включает объемный учебный лабораторный проект. Для подготовки к его выполнению, а также для контроля знаний студентов в течение семестра и на экзамене, в пособии разработано большое количество контрольных, тестовых заданий.

Значение Численных методов во многих областях науки и техники трудно переоценить, оно растет очень быстро. В связи с этим важно, чтобы студенты, готовящиеся стать специалистами в области математического моделирования, численных методов и комплексов программ, обладали подлинно глубокими знаниями, т. е. знаниями, имеющими для них практическую ценность в их будущей деятельности. Такое знание достигается не схоластическим изучением теории и не решением элементарных задач в классе, но реальной проектной работой по созданию серьезных программных продуктов высокого профессионального уровня, воплощающих эти численные методы. В связи с этим данное пособие использует так называемый проектно-ориентированный подход [134], при котором студенты получают необходимый теоретический материал и закрепляют эти знания в практических лабораторных проектах. После этого итоговая проверка знаний по курсу Численные методы – I проводится в форме решения задач на экзамене или же методом тестирования. Последнее предполагает умение быстро отыскивать правильный ответ, решать простые задачи и анализировать алгоритмы. Надеемся, что при таком подходе к преподаванию и изучению студент лучше поймет и оценит этот важный предмет.

Предисловие Разработка данного пособия велась на протяжении многих лет преподавания этого предмета в Ульяновском государственном университете и в Ульяновском государственном техническом университете. В этой работе в разное время участвовали коллеги: профессор Г. Ю. Куликов (Dr. Gennady Kulikov, CEMAT (Centro de Matemtica e Aplicaes), Instituto Superior Tcnico, LISBOA) e подготовил раздел по решению систем с разреженными матрицами; к. ф.-м. н., доцент Ю. В. Цыганова (Ульяновский государственный университет) выверяла текст, уточняла наши критерии учебной работы студента (разд. 1) и помогала готовить материал (подразд. 13.7) по устойчивым алгоритмам фильтрации; аспирант К. В. Захаров применил алгоритмы оценивания для решения прикладной (нелинейной) задачи сопровождения судна на траектории с маневрированием (подразд. 13.12);

к. ф.-м. н. М. В. Куликова (Dr. Maria Kulikova, Research Fellow at Universidade Tcnica de Lisboa, Instituto Superior Tcnico, CEMAT (Centro de Matemtica e Aplicaes), LISBOA) готовила материал по блочным алгоритмам оцениco вания (разд. 14) и обосновала ряд новых алгоритмов (разд. A.1). Выражаю моим коллегам благодарность за их вклад в подготовку пособия, за исследовательскую работу и поддержку этого важного направления.

Я признателен уважаемым рецензентам за время, которое они уделили для прочтения рукописи, и за их полезные рекомендации, которые я старался, по возможности, учесть. Конечно, все ошибки, которых не удалось избежать в этой работе, мои; мне будет приятно, если внимательные студенты их заметят.

Должен сказать, что включение обширного и в значительной мере справочного материала, составившего Часть II, поддержано интересом, который проявил к нему профессор доктор технических наук К. К. Васильев во время рецензирования одной из наших статей на тему вычислительных методов оценивания.

Прохождению материала в печать и его типографскому оформлению оказали содействие и помощь дирекция и сотрудники издательства УлГТУ.

Всем, кто прямо или косвенно способствовал выходу в свет этого издания и улучшению его качества, приношу свою благодарность.

Ульяновск, декабрь Введение 1.1 Учебные цели студента Мы живем в высокотехнологичном мире, в котором компьютер с каждым днем становится все более неотъемлемой частью. К тому же, наше общество все больше зависит от математики. Любая проблема решается лучше, если для нее найдена или построена подходящая (удовлетворительная, т. е.

адекватная) математическая модель. При том, что для этого может потребоваться различный объем математических знаний, каждому, кто берется решать математически ориентированные проблемы, необходимо иметь навыки аналитического мышления.

Допустим, вы этим обладаете и смогли придать задаче математическую форму, т. е. дали правильную математическую постановку задачи; вопрос заключается в том, существует ли для этой задачи аналитическое решение?

Действительность такова, что множество задач, для которых аналитическое решение существует и может быть найдено в конечной форме, невелико.

Большинство задач требует численных методов для своего решения. Особенность же этой области знания в том, что наилучшего численного метода обычно не существует, так как в одних условиях лучшим будет один метод, в то время как для других условий успешнее работает другой метод. Понять и обосновать, какой же метод выбрать как лучший, можно лишь проводя вычислительные эксперименты с различными методами и для различных задач и условий. Для этого нужно уметь осознанно планировать вычислительные эксперименты, понимать и правильно программировать численные методы и эффективно использовать возможности вычислительной техники.

Таким образом, безусловно каждому из вас потребуется хорошая компьютерная подготовка, чтобы выжить на рынке труда и успешно функционировать среди грамотных компьютерных пользователей. Было бы образовательВведение ным преступлением получить диплом выпускника университета и не иметь этих навыков хотя бы на удовлетворительном уровне. В конце концов, для этого вы и посещаете курсы информатики, программирования и численных методов.

Курс численных методов способствует этому, давая богатый набор индивидуальных заданий. В этом курсе мы преследуем три конкретные цели:

1. Студенты научатся выводить и доказывать положения математической теории численных методов, т. е. разовьют навыки аналитического мышления. Эти навыки будут проверены посредством финального экзамена.

2. Студенты увидят, как математика и компьютеры применяются к проблемам реального мира, т. е. научатся решать задачи. Эти умения будут проверены посредством семестровых контрольных работ, которые мы рассматриваем как часть распределенного по времени экзамена.

3. Студенты приобретут реальный опыт разработки компьютерных программ высокого (почти профессионального) уровня и применения компьютеров посредством написания, отладки и многочисленных прогонов своих программ. Приобретенный опыт будет проверен посредством выполнения домашних заданий на лабораторные работы, которые по своей значимости можно трактовать как своего рода учебные программные проекты.

1.2 Оценка работы студента Выставление финальной оценки. Для оценки того, в какой мере студент приблизился к своим целям навыки, умения и опыт, мы применяем следующую систему оценок.

Ваша оценка есть взвешенное среднее посещаемости (A), домашней работы (H) и экзаменов (E), где под экзаменами (см. подробнее ниже) понимается учет не только финального экзамена (во время сессии), но и контрольных работ в течение семестра:

Этот вес действует только в случае, если вы посещаете занятия. Если вы пропускаете занятия, этот вес прогрессивно возрастает (см. ниже). Вы можете получить неудовлетворительно исключительно в результате низкой посещаемости.

Таким образом, итоговая оценка (nal grade, F G) вычисляется по правилу:

где каждая составляющая:

A attendance (посещаемость), H homework (домашняя работа) и выражается целым числом не выше 100 баллов.

Эта итоговая оценка затем отображается на стандартную шкалу оценок:

Пример.

Студент Иван С. имеет следующие баллы:

A = 90, H = 87, E = 83. Тогда 0.05 90 + 0.30 87 + 0.65 83 = 84.6.

Следовательно, Иван заработал отлично.

Имейте в виду, что оценки зарабатываются.

Мы оставляем за собой право дать своего рода плюс-минус дельта, если студент имеет оценку на границе между оценками (т. е. 82, 70 или 55). Если студент имеет 90 или выше за посещаемость (A 90), сдал все домашние задания в установленный срок и проявил хорошее прилежание, тогда мы рассматриваем возможность выставления ему следующей более высокой оценки. Если же студент не продемонстрировал указанных выше качеств, возможность повышения оценки исключается. Мы не рассматриваем возможности повышения оценки, если до граничного значения не хватает хотя бы одного балла.

Для итоговой оценки мы используем симметричное округление, т. е.

округляем вверх, если младшая цифра есть 5 или выше, и вниз, если она меньше пяти. При вычислении средней оценки за домашнюю работу и средней за экзамены соответствующие числа H и E округляются до ближайшей десятой и затем они умножаются на свои весовые коэффициенты 0.05 и 0.30; после сложения по формуле (1.1) финальная оценка округляется.

Введение Учет посещаемости (A) Каждое учебное занятие, в том числе лекция, начинается с вашей росписи в явочном листе. Поставить свою роспись ваша личная ответственность. Отсутствие росписи означает ваше отсутствие на занятии.

Чтобы ваше отсутствие было расценено как уважительное, вы должны известить об этом преподавателя своевременно (т. е. в течение одной недели до или после занятия). Пожалуйста, оставьте преподавателю телефонное сообщение на рабочий телефон (секретарю кафедры) или Ваша оценка за посещаемость будет определена по табл. 1.1.

Таблица 1.1. Влияние неуважительных пропусков на оценку Неуважительный пропуск есть пропуск занятия, который не связан с болезнью, с семейной утратой или с факультетским мероприятием.

При числе неуважительных пропусков выше десяти у вас нет шанса получить положительную итоговую оценку за весь курс.

Вы можете иметь максимум 8 уважительных пропусков. После этого все пропуски считаются неуважительными.

Для спортсмена пропуск занятия считается уважительным, если его тренер известит об этом преподавателя заранее в письменной форме.

Если вы больны, позвоните на кафедру, чтобы преподавателя об этом известили. Любой такой пропуск будет неуважительным, если преподавателя не известят в течение одной недели после вашего пропуска занятия. Извещение следует делать в форме телефонного сообщения или записки секретарю кафедры. Ваше извещение должно содержать номер группы, день и время пропускаемого занятия, название предмета и, конечно, ваше имя и фамилию.

Домашняя работа (H) Вам будет предложен ряд домашних заданий, которые по нашему предположению вы выполните и сдадите. Баллы за отдельные задания складываются и тем самым образуют H, т. е. оценку за этот вид вашей учебной работы. Любая сдача домашнего задания позже установленного срока влечет уменьшение вашей оценки H на 10 баллов. За каждое невыполненное задание в H поступает 0.

Домашние задания представляют собой задания на лабораторные работы (проекты). Обычно мы предлагаем выполнить 3 таких работы за семестр, т. е. выдаем 3 задания. Максимальное количество баллов H, которое можно заработать за всю домашнюю работу, составляет 100. Эти 100 баллов мы разделяем определенным образом между общим числом выданных домашних заданий.

Предлагаемые каждому студенту 3 лабораторные работы на первый семестр покрывают три темы из списка на стр. 12, включенные в данное пособие. За выполненное безупречно и в полном объеме задание по теме № 1 (это любой, по выбору студента или преподавателя, лабораторный проект №№ 1, 2, 3 или 4) студент заработает 50 баллов, причем по срокам это задание должно предшествовать всем последующим. Далее, за выполненное безупречно и в полном объеме задание по теме № 2 (это лабораторный проект № 5) студент заработает 20 баллов, а за выполненное безупречно и в полном объеме задание по теме № 3 (это лабораторный проект № 6) 30 баллов. Заработанное число баллов за каждое задание будет уменьшено, если защита работы не отвечает всем требованиям, изложенным в данном учебном пособии, или не демонстрирует самостоятельность выполнения. Следующие по номерам проекты предлагаются в рамках дополнительного семестра или как курсовые работы.

Введение Преподаватель, ведущий лабораторные занятия в дисплейном классе, назначит сроки сдачи лабораторных работ и на каждом занятии всегда с готовностью поможет вам, если вы ясно формулируете те конкретные вопросы, которые у вас возникли дома. Преподаватель, ведущий семинарские (практические) занятия, поможет вам и всей аудитории, когда вы будете у доски рассказывать, как вы понимаете и как дома программируете тот или иной алгоритм.

Экзамены (E) Ваша оценка за экзамены, т. е. величина E в составе финальной оценки, вычисляемой по формуле (1.1), будет определена как равномерно взвешенное среднее значение результатов PКР–1, PКР–2 и PКР–3 трех письменных контрольных работ (КР–1), (КР–2) и (КР–3) в течение семестра и результата PУЭ устного экзамена (УЭ) во время экзаменационной сессии.

При том, что контрольные работы письменно проверяют ваше умение решать задачи, устный экзамен есть всеобъемлющая проверка вашего знания основных положений теории, умения доказывать эти положения и делать из них логические выводы. Эти (письменная и устная) части экзамена в совокупности покрывают весь учебный курс. Для этого мы проводим обычно три контрольные работы за семестр.

Все контрольные работы будут вам объявлены заранее не позднее, чем за неделю. Если вы собираетесь пропустить контрольную работу (это должен быть уважительный пропуск), мы предпочтем, чтобы вы написали эту работу раньше назначенного срока. Если вы не сможете написать контрольную работу до назначенного срока, то примите все меры к тому, чтобы написать ее в течение недели после контрольного срока. По истечении недели после этого вы получите ноль. Вы также получите ноль за неуважительный пропуск контрольной работы.

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

1.3 Кодекс студента Академическая честность К сожалению, есть люди, не столь честные, как другие, и настолько, что мы должны пояснить, как будем действовать в этом случае.

За любую контрольную работу, экзамен, программу или любой иной вид работы, который выполнен нечестно, вы получите ноль, и преподаватель будет беседовать с вами. Если такая проблема случится во второй раз, преподаватель направит вас к декану факультета, и вы снова заработаете ноль за этот вид работы. Если вопрос о нечестности возникнет в третий раз, то вы сразу заработаете неудовлетворительно за весь предмет и снова будете отправлены к декану.

Что считается академической нечестностью, т. е. обманом? По общепринятому правилу, это означает найти кого-то другого, кто сделает за вас вашу работу, и выдать ее за вашу собственную. Это также включает получение и оказание посторонней помощи на экзамене или во время контрольной работы (от соседа или с помощью шпаргалки).

Наши экзамены это всегда закрытая книга, закрытый конспект, закрытый сосед и открытый ум. Если в этом правиле появятся какиелибо изменения, об этом будет объявлено заранее.

Не пользуйтесь шпаргалками. Они приносят больше вреда, чем пользы.

Ваше сознание будет раздвоено между попыткой сформулировать ответ и попыткой утаить факт пользования шпаргалкой. Обнаружить такое раздвоенное сознание не составляет никакого труда. Вы будете обескуражены еще больше самыми простыми вопросами экзаменатора.

При выполнении домашних заданий приемлемо работать с кем-то еще, обсуждая трудные вопросы и помогая тем самым друг другу, но при этом вы должны сами делать свою работу. Например, при написании компьютерных программ вполне нормально обсуждать синтаксис, детали задания или получать помощь по сообщениям об ошибке. Ненормально, если вы отдаете кому-то копию вашей программы. Неприемлемо, если кто-то другой пишет программу для вас. Недопустимо копировать работу предыдущего семестра.

гиатом является дословное копирование части чужих трудов, таких как чья-то статья (в том числе и опубликованная в Интернете), книга Введение или энциклопедия, без использования кавычек и ссылки на источник.

Обобщающие заключения и выводы, которые вы пишете, должны быть выражены вашими собственными словами.

Нечестность, когда она появляется в домашней работе, не столь очевидна. Мы это вполне признам. Но она так или иначе проявит себя на устном экзамене, так как ваш балл за домашнюю работу будет контрастировать с уровнем вашего ответа. Вы только навредите себе и осложните свое положение очевидной провинностью.

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

Поднимайте руку и ждите, когда на вас обратят внимание, перед тем Не разговаривайте в аудитории.

Уберите за собой и поставьте стул в исходное положение.

Приходите на занятие вовремя, принимайте в нем участие и ведите Просматривайте задания до занятия.

Проверяйте ваши записи после занятия.

Вовремя выполняйте ваши задания.

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

Выполняйте рекомендации по подготовке к контрольным работам и к финальному экзамену. Убедитесь, что вы можете решать типовые задачи и доказывать теоремы, которые во время лекций были отмечены как упражнения для самостоятельной работы.

Придерживайтесь твердой решимости добиться успеха.

Если вам нужна помощь, получайте ее безотлагательно.

Сохраняйте позитивное отношение к делу.

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

Преподаватель периодически просматривает свой сайт. Вы можете посылать через него ваши кратко сформулированные предложения, которые, по вашему мнению, помогли бы вам повысить эффективность изучения этого предмета.

Добро пожаловать на наши занятия. Вместе мы рассчитываем на большой и продуктивный семестр!

1.4 Краткое описание курса Этот примерный план (стр. 24) может незначительно варьироваться в соответствии с новыми образовательными стандартами.

Как бы ни называлась дисциплина, соответствующая курсу Численные методы, Вычислительная математика или Методы вычислений, главная отличительная особенность нашего курса и данного пособия выражается в следующем диалоге, который иногда возникает между Студентом и Экзаменатором (автором данного пособия):

Студент: Я знаю этот численный метод и хочу получить более высокую оценку.

Экзаменатор: Если вы хорошо знаете этот метод, так научите этому компьютер.

Введение

ЧИСЛЕННЫЕ МЕТОДЫ (АЛГЕБРЫ)

Формат:

Преподаватель: проф. И. В. Семушин, доц. Ю. В. Цыганова Содержание:

Этот курс излагает численные методы решения задач линейной алгебры: решение систем уравнений, обращение матриц, вычисление определителей, решение нелинейных уравнений, аппроксимация функций и отыскание собственных значений матриц. Программа курса охватывает: методы исключения неизвестных, разложения Холесского, ортогональные преобразования, итерационные методы, метод наименьших квадратов, устойчивые алгоритмы оценивания и обзор методов решения проблемы собственных значений.

Ожидаемые результаты изучения: продемонстрировать структуры погрешностей решения вычислительных задач; корректности задач; прямых и итерационных методов для систем знание и уравнений; задачи и алгоритмов метода наименьших квадратов;

понимание:

понимать и формулировать основные численные процедуры и способность:

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

понимать реализацию и поведение численных методов и решеспособность:

ний на практике; логически формулировать численные методы (практические для решения задач на компьютере с применением языков пронавыки) изучать предмет самостоятельно; использовать литературные способность:

источники; использовать персональный компьютер для проключевые граммирования; эффективно конспектировать материал и раснавыки) Оценивание: 5 % за посещаемость (неуважительные пропуски прогрессивно штрафуются); 30 % за семестровые (домашние) задания, 65 % суммарно за три контрольные работы и финальный (устный) экзамен.

Практическая работа: Выдаваемые индивидуальные задания включают программирование отдельных методов из числа методов, излагаемых в данном курсе.

Рекомендуемые учебные материалы: Конспект лекций.

В. В. Воеводин. Численные методы алгебры. Теория и алгоритмы. М.: Наука, 1966.

А. А. Самарский, А. В. Гулин. Численные методы. М.: Наука, 1989.

Дополнительное чтение: Н. Н. Калиткин. Численные методы. М.: Наука, 1978.

Н. С. Бахвалов. Численные методы. М.: Наука, 1975. или: Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. Численные методы. М.: Наука, 1987.

Число кредитных часов (приравнивается числу аудиторных часов в неделю).

Продолжительность курса.

Вычислительная линейная алгебра Стандартные алгоритмы LU -разложения 2.1 Алгоритмы метода Гаусса Обычный метод Гаусса, осуществляющий LU -разложение матрицы A [12, 5, 4, 9, 97], заключается в последовательном исключении переменных из уравнений системы На первом шаге для исключения первой переменной x1 из всех уравнений, лежащих в системе ниже первого уравнения, первое уравнение объявляем ведущим уравнением. Это возможно только при a11 = 0. Тогда, разделив обе части (2.2) на a11, это ведущее уравнение получим в виде, в котором коэффициент при x1 окажется равен 1. Заметим, что эта 1 строгая (т. е. не приближенная) величина. Это действие деление уравнения на ровкой.

Второе действие заключается в серии вычитаний ведущего уравнения из всех нижележащих уравнений, чтобы исключить из них неизвестную x1. Для этого умножаем пронормированное уравнение на ai1 и вычитаем результат из i-го уравнения системы (2.1), i = 2,..., n. На этом заканчивается первый шаг алгоритма. После первого шага система (2.1) приведена в виду:

2 Стандартные алгоритмы LU-разложения Это второе действие удобно называть обновлением активной подсистемы (активной подматрицы), т. е. той части системы уравнений (матрицы A), где еще будут продолжаться подобного рода действия.

На втором шаге метода Гаусса описанный алгоритм повторяем для переменной x2, т. е. берем систему (2.3), объявляем ведущим второе уравнение (для этого нужно иметь a22 = 0) и нормируем в ней второе уравнение.

Получаем его в виде (верхний индекс в скобках указывет номер шага, после которого получен текущий результат). После этого исключаем переменную x2 из оставшихся n 2 уравнений системы (2.3). Таким образом, любой полный шаг алгоритма метода Гаусса состоит из двух действий: сначала нормировка ведущей строки матрицы, потом обновление (серия вычитаний) в активной подматрице.

После n 1 полных шагов и n-го неполного шага (поскольку ниже n-го ведушего уравнения больше нет уравнений) получим две системы линейных алгебраических уравнений эквивалентных исходной системе (2.1), где L нижняя треугольная матверхняя треугольная матрица, на диагонали которой стоят едирица и U ницы1. При этом k-й столбец матрицы L (его нетривиальная, т. е. ненулевая часть) запоминает числа для двух действий на k-м шаге алгоритма, а именно: элемент lkk является ведущим элементом, производившим нормировку k-го уравнения, в то время как элементы lki, i = k + 1, k + 2,..., n являются теми коэффициентами, на которые было умножено пронормированное ведущее (k-е) уравнение, чтобы результатом последующего его вычитания из нижележащих уравнений было исключение из них неизвестного xk.

Можно говорить, что роль матрицы L сохранять историю нормировок и вычитаний в процессе исключения неизвестных по методу Гаусса. Роль матрицы U иная. Матрица U представляет собою тот эквивалентный вид системы (2.1), который она приобретет по завершении этого процесса.

Определение 2.1. Определители i подматриц, получаемых оставлением первых i строк и первых i столбцов матрицы, называют главными минорами матрицы.

Здесь и далее черта над матрицей означает, что на главной диагонали стоят строгие единицы.

Теорема 2.1. Если все главные миноры матрицы A в системе (2.1) отличны от нуля, то процесс Гаусса исключения неизвестных, протекающий в прямом направлении, начиная от первого неизвестного x1 и от первого уравнения системы, эквивалентен разложению A = LU, которое существует и единственно с нижней треугольной невырожденной матрицей L и верхней треугольной матрицей U с единичной диагональю.

Доказательство.

После разложения вводят правую часть f данной системы (2.1) и находят вектор y решения называется прямой подстановкой:

Далее вторая система из (2.4) так же легко решается процедурой обратной подстановки:

Замечание 2.1. Пересчет элементов вектора f должен быть отложен, т. е. сначала пересчет коэффициентов матрицы A должен привести к разложению матрицы A в произведение матриц L и U и только затем должна быть введена и соответственно обработана правая часть вектор f. При этом вектор y замещает f и затем x замещает y, экономия памяти.

Алгоритм LU -разложения матрицы A запишем следующим образом:

Нормируем первую строку матрицы A(k1).

Здесь A(k1) означает активную подматрицу матрицы A после (k 1)-гo шага метода Гаусса, k = 1, 2,..., n, причем A(0) = A.

Алгоритм LU -разложения матрицы A отличается только нормировкой элементов активной подматрицы:

2 Стандартные алгоритмы LU-разложения Нормируем первый столбец матрицы A(k1).

Упражнение 2.1. Измените направление процесса Гаусса на обратное. Докажите, что если процесс Гаусса исключения неизвестных вести от последнего неизвестного xn и от последнего уравнения системы, двигаясь вверх по нумерации уравнений и влево по нумерации исключаемых неизвестных, то получим разложение A = U L (если нормировать строки) и A = U L (если нормировать столбцы). Докажите соответствующие теоремы аналоги теоремы 2.1. Для этого измените определение 2.1 главных миноров.

Описанные выше алгоритмы в том виде, в каком они приведены, на практике используются очень редко, т. е. только в том случае, если можно гарантировать, что в результате гауссова исключения на диагонали не появятся нулевые элементы. Однако это можно гарантировать только для матриц специального вида (например, для положительно определенных матриц, см. разд. 6), поэтому в общем случае используется метод Гаусса с выбором главного (ведущего) элемента.

2.2 Выбор ведущего элемента Определение 2.2. Матрицей перестановок P называют квадратную матрицу, в которой каждая строка, а также каждый столбец, содержит один ненулевой элемент, равный 1.

Определение 2.3. Элементарной матрицей перестановок Pij называют квадратную матрицу, полученную из единичной матрицы перестановкой двух строк: i-й и j-й, либо перестановкой двух столбцов: i-го и j-го (оба варианта перестановок дают один и тот же результат).

Упражнение 2.2. Докажите справедливость следующих утверждений:

1. Произведение Pij A производит в A перестановку i-й и j-й строк.

2. Произведение APij производит в A перестановку i-го и j-го столбцов.

3. Pij Pij = I 4. Любая матрица перестановок P может быть разложена в произведение элементарных матриц перестановок.

5. P 1 = P T свойство ортогональности матриц перестановок P.

Теорема 2.2. Если det A = 0, то существуют матрицы перестановок P и Q, такие что все угловые (т. е. главные) миноры матрицы P A, равно как и матриц AP и AP Q, отличны от нуля.

Доказательство. Докажите индукцией по размеру матрицы A [12]. Следствие 2.1. Если det A = 0, то существуют матрицы перестановок P и Q, такие что следующие варианты разложения матрицы A существуют и единственны: P A = LU, P A = LU, AP = LU, AP = LU, P AQ = LU, Отсюда видны три стратегии выбора главного (ведущего) элемента: по столбцу, по строке и по активной подматрице.

Стратегия I. Первая стратегия (по столбцу) подразумевает, что в качестве главного на k-м шаге метода Гаусса выбирается максимальный по модулю элемент первого столбца активной подматрицы. Затем этот элемент меняется местами с диагональным элементом, что соответствует перестановке строк матрицы A(k1) и элементов вектора f (k1). На самом деле строки матрицы A(k1) и элементы вектора f (k1) остаются на своих местах, а переставляются только элементы дополнительного вектора, в котором хранятся номера строк исходной матрицы, соответствующие номерам строк матрицы, т. е. элементы так называемого вектора перестановок. Все обращения к элементам матриц L, U и вектора f осуществляются через вектор перестановок.

Стратегия II. Следующая стратегия (по строке) заключается в выборе в качестве главного элемента максимального по модулю элемента первой строки активной подматрицы. Затем этот элемент обменивается местами с диагональным, что соответствует перестановке столбцов матрицы A(k1) и элементов вектора x. Как и в предыдущем случае, реально обмениваются только элементы дополнительного вектора, в котором фиксируются перестановки столбцов матрицы A. Доступ к элементам матриц L, U и вектора x осуществляется с использованием этого вектора.

2 Стандартные алгоритмы LU-разложения Стратегия III. Последняя стратегия выбора главного элемента (по активной подматрице) объединяет две первые стратегии. Здесь в качестве главного выбирается максимальный по модулю элемент активной подматрицы. В общем случае, чтобы поставить этот элемент на место диагонального, требуется обменивать столбцы и строки матрицы A(k1), что связано с введением двух дополнительных векторов: в одном хранятся перестановки столбцов, а в другом перестановки строк матрицы A.

Приведенные выше алгоритмы LU -разложения с учетом выбора главного элемента преобразуются к одному из следующих вариантов.

Алгоритм 1. LU-разложение по методу Гаусса Нормируем первую строку матрицы A(k1).

Алгоритм 2. LU -разложение по методу Гаусса Нормируем первый столбец матрицы A(k1).

Вышеприведенные алгоритмы называют исключением по столбцам, так как они исключают xk из всей поддиагональной части k-го столбца.

Замечание 2.2. Во всех алгоритмах должно быть выполнено требование к реализации: все действия должны выполняться в одном и том же массиве чисел. Например, в Алгоритме 1 сначала A(0) = A, а в конце на месте этой матрицы получаются нетривиальные элементы матриц L и U.

Замечание 2.3. Под выбором главного элемента здесь и далее понимается любая из описанных выше трех стратегий, которая применима.

Замечание 2.4. При U L-разложении матрицы A все действия выполняются аналогично, но в обратном порядке нумерации строк и столбцов: снизу-вверх и справа-налево.

Наряду с гауссовым исключением по столбцам, представленным выше, возможно проводить гауссово исключение по строкам. Это такая разновидность метода Гаусса, в которой на каждом шаге исключения изменяется первая строка активной подматрицы. Рассмотрим гауссово одна строка исключение по строкам с выбором главного элемента по строке.

Выполняем i-й шаг, т. е. работаем с i-й строкой матрицы. В ней еще не было ни одного исключения неизвестных. Первое действие: из i-й строки вычитаем первую, умноженную на ai1; затем из i-й строки вычитаем вторую, умноженную на ai2, и так далее; в завершение этой серии вычитаний из i-й строки вычитаем (i 1)-ю, умноженную на ai(i1). Второе действие: отыскиваем главный элемент в i-й строке и осуществляем (если надо) перестановку столбцов. Третье действие: i-ю строку нормируем (делим на ведущий элемент). Повторяя этот алгоритм n раз, получим LU -разложение матрицы AP. При i = 1 шаг, очевидно, неполный, т. е. без вычитаний.

Таким образом, отличие гауссова исключения по строкам от гауссова исключения по столцам сводится в алгоритме к изменению порядка действий: сначала серия вычитаний, а затем нормировка. Такая возможность (для варианта A = LU) представлена в следующем алгоритме.

Алгоритм 3. LU -разложение по методу Гаусса (по строкам) Замечание 2.5. В описаниях алгоритмов упоминаются элементы матрицы A. Естественно, речь идет о текущих, а не об исходных значеСтандартные алгоритмы LU-разложения ниях элементов, занимающих указанные позиции матрицы A. Это связано с выполнением требования к реализации (см. Замечание 2.2).

2.3 Компактные схемы Следующей разновидностью метода Гаусса являются компактные схемы.

Первая называется компактной схемой Краута, а вторую мы будем называть компактной схемой Краута строка за строкой. В схеме Краута на каждом шаге исключения изменяются только первый столбец и первая строка активной подматрицы. В схеме строка за строкой на k-м шаге изменяется только k-я строка матрицы A.

Выведем формулы схемы Краута для k-го шага. Предположим, что уже сделаны первые k 1 шагов, т. е. определены k 1 столбец матрицы L и k строка матрицы U. Из соотношения A = LU для (i, j)-гo элемента имеем В силу треугольности матриц L и U при p > i имеем lip = 0 и при p > j имеем upj = 0. Тогда с учетом того, что ukk = 1, для k-го столбца матрицы A находим Из (2.6) следует Следовательно, k-й столбец матрицы L становится известен. Теперь из (2.5) для k-й строки матрицы A имеем Из (2.8) находим Таким образом, (2.9) дает способ нахождения k-й строки матрицы U. В результате, зная первые k 1 столбцов матрицы L и k 1 строк матрицы U, мы можем по формулам (2.7) и (2.9) определить k-й столбец матрицы L и затем k-ю строку матрицы U. Первый столбец матрицы L определяется равенствами Это следует из (2.7) и того, что первым столбцом матрицы U является первый координатный вектор e1. Здесь, как обычно, предполагаем, что если нижний предел суммирования меньше верхнего, то значение суммы равно нулю. После этого в первом столбце выбираем главный элемент. Затем по формулам вычисляем первую строку матрицы U. Повторяя указанную последовательность действий n раз, с помощью формул (2.7) и (2.9) получаем LU -разложение матрицы A.

Алгоритм 4. LU -разложение по компактной схеме Краута По формуле (2.7) вычисляем k-й столбец матрицы L.

Выбираем среди элементов k-го столбца главный элемент.

По формуле (2.9) вычисляем k-ю строку матрицы U.

Чтобы получить метод Краута, дающий LU -разложение с выбором главного элемента по строке, достаточно поменять местами формулы (2.7) и (2.9), а также последовательность вычисления столбцов матрицы L и строк матрицы U. Таким образом, на k-м шаге сначала по формуле вычисляется строка матрицы U. Затем в этой строке выбирается главный элемент и находится столбец матрицы L по следующей формуле:

2 Стандартные алгоритмы LU-разложения Упражнение 2.3. Выведите расчетные формулы компактных схем для любого из альтернативных вариантов разложения: A = U L или A = U L.

Что изменяется? Дайте ответы в форме условных схем алгоритмов, представленных непосредственно до и после этого упражнения.

Алгоритм 5. LU -разложение по компактной схеме Краута По формуле (2.10) вычисляем k-ю строку матрицы U.

Выбираем среди элементов k-й строки главный элемент.

По формуле (2.11) вычисляем k-й столбец матрицы L.

Компактная схема строка за строкой, дающая LU-разложение матрицы A, использует те же самые формулы (2.7) и (2.9). Меняется только последовательность вычисления элементов матрицы L. Рассмотрим подробнее.

Пусть уже обработаны по этому методу первые k 1 строк матрицы A.

Следовательно, мы имеем k 1 строку матрицы L и k 1 строку матрицы U. Далее по формулам (2.7) вычисляем ненулевые элементы k-й строки матрицы L. По формулам (2.9) без деления на диагональный элемент lkk вычисляем ненулевые элементы k-й строки матрицы U. Затем среди вновь вычисленных элементов, от диагонального до n-го, определяем главный элемент, меняем его местами с диагональным и делим элементы k-й строки матрицы U на этот элемент. В результате получаем требуемое разложение.

Алгоритм 6. LU-разложение по компактной схеме По формуле (2.7) вычисляем элементы k-й По формуле (2.9) без деления на диагональный элемент lkk, вычисляем k-ю строку матрицы U.

Среди элементов k-й строки (от диагонального до n-го) определяем главный элемент.

Делим на главный элемент k-ю строку матрицы U.

2.4 Алгоритмы метода Жордана К последней группе методов исключения относятся алгоритмы метода Жордана. Эти алгоритмы используют те же самые формулы, что и обычный метод Гаусса, но в отличие от него на k-м шаге метода Жордана пересчитывают все строки матрицы A, а не только строки, находящиеся ниже ведущей строки. Это означает полное исключение i-й переменной из всех уравнений, кроме i-го. Таким образом, метод Жордана формально дает решение системы линейных алгебраических уравнений за один проход.

Теорема 2.3. Выполнение действий полного исключения в том же массиве, где первоначально располагалась матрица A, дает то же самое разложение A = LU, что и метод Гаусса, но существенно в другом виде, а именно: матрица L получается, как и в методе Гаусса, но матрица U оказывается полученной не в чистом виде, а в виде обратной матрицы U 1 и с той особенностью, что все знаки элементов матрицы U 1 выше диагонали имеют неправильные (противоположные) знаки.

Доказательство. Нужно воспользоваться определениями элементарных матриц специального вида [10] и их свойствами. Приведем эти определения и свойства и затем продолжим доказательство.

Определение 2.4. Элементарная матрица E есть любая матрица вида E = I + B, где rank B = 1.

векторы.

Определение 2.5.

матрицы:

Dk диагональная k-матрица. Имеет единичную диагональ, кроме k-го элемента, который не тривиален, т. е. не равен нулю или единице.

LC столбцово-элементарная нижняя треугольная k-матрица. Имеет едиk ничную диагональ и нетривиальные элементы только в k-м столбце.

LR строчно-элементарная нижняя треугольная k-матрица. Имеет едиk ничную диагональ и нетривиальные элементы только в k-й строке.

Uk столбцово-элементарная верхняя треугольная k-матрица. Имеет единичную диагональ и нетривиальные элементы только в k-м столбце.

2 Стандартные алгоритмы LU-разложения Таблица 2.1. Свойства специальных элементарных матриц 5. Матрица из пункта 4, но 2 Стандартные алгоритмы LU-разложения Вычисления проводить при близком к нулю или.

7. Матрица с параметром :

Вычисления проводить при h близких к нулю или 1000.

Вычисления проводить при больших c.

2.7 Задание на лабораторный проект № Написать и отладить программу, реализующую ваш вариант метода исключения с выбором главного элемента, для численного решения систем линейных алгебраических уравнений Ax = f, вычисления det A и A1.

Предусмотреть сообщения, предупреждающие о невозможности решения указанных задач с заданной матрицей A.

Отделить следующие основные части программы:

а) подпрограмму факторизации матрицы A, отвечающую вашему варианту метода исключения;

б) подпрограмму решения систем линейных алгебраических уравнений;

в) подпрограмму вычисления определителя матриц;

г) две подпрограммы обращения матриц;

д) сервисные подпрограммы.

Уделить особое внимание эффективности программы (в смысле экономии оперативной памяти). Предусмотреть пошаговое выполнение алгоритма исключения с выводом результата на экран.

Выполнить следующие пункты задания.

1. Провести подсчет фактического числа выполняемых операций умножения и деления при решении системы линейных алгебраических уравнений, сравнить его с оценочным числом (n3/3).

2. Определить скорость решения задач (решение систем линейных алгебраических уравнений, обращение матриц) с учетом времени, затрачиваемого на разложение матрицы. Для этого спроектировать и провести эксперимент, который охватывает матрицы порядка от 5 до 100 (через 5 порядков). Представить результаты в виде таблицы и графика зависимости времени выполнения (в минутах и секундах) от порядка матриц. Таблицу и график вывести на экран.

3. Оценить точность решения систем линейных алгебраических уравнений, имеющих тот же самый порядок, что и задачи из п. 2. Для этого сгенерировать случайные матрицы A, задать точное решение x и образовать правые части f = Ax. Провести анализ точности вычисленного решения x от порядка матрицы. Результаты представить в виде таблицы и графика.

Для заполнения матрицы A использовать случайные числа из диапазона от 100 до 100. В качестве точного решения взять вектор x = (1, 2,..., n)T, где n порядок матрицы. Для оценки точности использовать норму вектора 4. Повторить пункт 3 задания для плохо обусловленных матриц (см. подразд. 2.6), имеющих порядок от 4 до 40 с шагом 4.

5. Вычислить матрицу A1 следующими двумя способами.

Способ 1 через решение системы AX = I, где I единичная матрица.

Способ 2 через разложение матрицы A в произведение элементарных матриц, обращение которых осуществляется отдельными процедурами, а их произведение дает матрицу A1.

Сравнить затраты машинного времени (по числу операций) и точность обращения матриц при использовании указанных способов 1 и 2. Эксперименты провести для случайных матриц порядков от 5 до 100 через 5. Для оценки точности в обоих способах использовать оценочную формулу 2 Стандартные алгоритмы LU-разложения Использовать норму матрицы типа бесконечность, т. е. вычислять ее по следующему выражению:

чение, полученное в результате обращения каждым из способов 1 и 2.

6. Провести подсчет фактического числа выполняемых операций умножения и деления при обращении матриц первым и вторым способами, сравнить его с оценочным числом (n3).

Замечание 2.8. По ходу проведения численных экспериментов на экран дисплея должны выводиться следующие таблицы.

Решение систем линейных алгебраических уравнений:

Аналогичная таблица должна быть построена для плохо обусловленных матриц.

Замечание 2.9. Результаты экспериментов необходимо вывести на экран в форме следующих графиков. Для случая обращения матриц при построении графиков использовать данные из второй таблицы.

Графики решения систем линейных алгебраических уравнений:

зависимость реального и оценочного числа операций от порядка матрицы (для разных графиков использовать разные цвета);

зависимость времени решения от порядка матриц;

зависимость точности решения от порядка матриц. При построении графиков использовать данные из первой таблицы. Для этого их необходимо записать в текстовый файл.

зависимость реального и оценочного числа операций от порядка матрицы (для разных графиков использовать разные цвета);

зависимость времени обращения первым и вторым способом от порядка зависимость точности обращения первым и вторым способом от порядка 2.8 Варианты задания на лабораторный проект № 1. LU-разложение на основе гауссова исключения по столбцам с выбором главного элемента по столбцу.

2. LU-разложение на основе гауссова исключения по столбцам с выбором главного элемента по строке.

3. LU-разложение на основе гауссова исключения по столбцам с выбором главного элемента по активной подматрице.

4. LU -разложение на основе гауссова исключения по столбцам с выбором главного элемента по столбцу.

5. LU -разложение на основе гауссова исключения по столбцам с выбором главного элемента по строке.

6. LU -разложение на основе гауссова исключения по столбцам с выбором главного элемента по активной подматрице.

7. LU -разложение на основе гауссова исключения по строкам с выбором главного элемента по строке.

8. LU -разложение по компактной схеме Краута с выбором главного элемента по столбцу.

9. LU -разложение по компактной схеме Краута с выбором главного элемента по строке.

10. LU -разложение по компактной схеме строка за строкой с выбором главного элемента по строке.

11. LU 1-разложение A = LU на основе жорданова исключения с выбором главного элемента по столбцу.

12. LU 1-разложение A = LU на основе жорданова исключения с выбором главного элемента по строке.

13. LU 1-разложение A = LU на основе жорданова исключения с выбором главного элемента по активной подматрице.

2 Стандартные алгоритмы LU-разложения 14. U L-разложение на основе гауссова исключения по столбцам с выбором главного элемента по столбцу.

15. U L-разложение на основе гауссова исключения по столбцам с выбором главного элемента по строке.

16. U L-разложение на основе гауссова исключения по столбцам с выбором главного элемента по активной подматрице.

17. U L-разложение на основе гауссова исключения по столбцам с выбором главного элемента по столбцу.

18. U L-разложение на основе гауссова исключения по столбцам с выбором главного элемента по строке.

19. U L-разложение на основе гауссова исключения по столбцам с выбором главного элемента по активной подматрице.

20. U L-разложение на основе гауссова исключения по строкам с выбором главного элемента па строке.

21. U L-разложение по компактной схеме Краута с выбором главного элемента по столбцу.

22. U L-разложение по компактной схеме Краута с выбором главного элемента по строке.

23. U L-разложение по компактной схеме строка за строкой с выбором главного элемента по строке.

24. L1U -разложение A = LU на основе жорданова исключения с выбором главного элемента по столбцу.

25. L1U -разложение A = LU на основе жорданова исключения с выбором главного элемента по строке.

26. L1U -разложение A = LU на основе жорданова исключения с выбором главного элемента по активной подматрице.

Если нет других указаний преподавателя, выбирайте ваш вариант по вашему номеру в журнале студенческой группы.

Векторно-ориентированные алгоритмы LU -разложения 3.1 Гауссово исключение и ijk-алгоритмы Рассмотрим систему линейных уравнений с невырожденной матрицей A размера (n n). Мы считаем A заполненной матрицей. Разреженные матрицы расматриваются в разд. 5.

Как изложено в подразд. 2.1, наиболее известной формой гауссова исключения является та, в которой система (3.1) приводится к верхнетреугольному виду путем вычитания одних уравнений, умноженных на подходящие числа, из других уравнений; полученная треугольная система решается с помощью обратной подстановки. Математически все это эквивалентно тому, что вначале строится разложение матрицы A, например вида A = LU, где L является нижнетреугольной матрицей с единицами на главной диагонали, а U верхнетреугольная матрица с ненулевыми элементами на диагонали. Затем решаются треугольные системы Процесс их решения называется, соответственно, прямой и обратной подстановками.

Мы сосредоточимся вначале на LU -разложении, поглощающем большую часть времени всего процесса, а затем вернемся к решению треугольных систем. Псевдокод разложения приведен на рис. 3.1.

В цикле j на рис. 3.1 кратные k-й строки текущей матрицы A вычитаются из расположенных ниже строк. Эти операции представляют собой триады, в которых векторами являются строки матрицы A [8].

3 Векторно-ориентированные алгоритмы LU-разложения Рис. 3.1. Строчно ориентированная Рис. 3.2. Столбцово ориентированная Определение 3.1. Триадой называют операцию вида a + b, где a и b суть векторы, а Определение триады появилось в связи с использованием векторных компьютеров 2, требующих, чтобы векторы располагались в последовательно адресуемых ячейках памяти. Для алгоритма на рис. 3.1 удобно предположить, что A хранится по строкам. Соответственно этому, схема на рис. 3. названа строчно ориентированной. В ней посредством триад осуществляется модификация (т. е. обновление) строк матрицы A; на это приходится основная часть работы в LU -разложении.

Реальные задачи, как правило, требуют выбора главного элемента, и это еще сильнее уменьшает скорость. При использовании одной из стратегий частичного выбора мы должны на первом шаге просмотреть первый столбец в поисках максимального по модулю элемента. Эта стратегия, соответственно, называется выбором главного элемента по столбцу, и она приводит к перестановке строк 3. Как только положение максимального элемента определено, соответствующую строку можно переставить с первой (точнее, текущей ведущей) строкой или изменить порядок индексации строк. Второй вариант называют неявной перестановкой строк. Как именно реализуется стратегия выбора главного элемента, зависит от вашего варианта задания.

Однако во всех вариантах лабораторных работ физическая, т. е. явная перестановка строк (или столбцов) запрещена и должна быть заменена изменением порядка нумерации строк (или столбцов), т. е. неявной перестановкой.

Это требование соответствует реальным пакетам вычислительной линейной алгебры. т. е. так в реальности всегда и делают. В схеме на рис. 3.1 возможны все три стратегии выбора главного элемента (см. подразд. 2.2).

В зарубежной литературе триаду называют также saxpy, что обозначает операцию y := ax + y и заменяет фразу: Single precision (с обычной точностью) ax Plus y.

По поводу триады и векторных компьютеров см. подразд. 3.2 и 3.3.

Подробнее о стратегиях выбора главного элемента см. подразд. 2.2.

Правая часть b системы (3.1) также может обрабатываться в ходе приведения системы к треугольному виду, благодаря чему осуществляется этап прямой подстановки в равенствах (3.2). Такая обработка правой части b, выполняемая одновременно с приведением матрицы A к треугольному виду, также запрещена во всех вариантах лабораторных работ (проектов). Это требование тоже отвечает реальности, так как позволяет экономить значительное время в условиях, когда требуется решать одну и ту же систему (3.1) с различными правыми частями. Ситуация такого рода обращение матрицы с помощью решения матричного уравнения AX = I, где I единичная матрица, т. е. нахождение X = A1. В этом случае правые части b вводятся в уравнения (3.2) последовательно. При вычислении i-го столбца матрицы X = A1 каждая правая часть равна очередному (i-му) столбцу единичной матрицы. Для каждого b в (3.2) сначала решают первую систему, т. е. вычисляют y, а затем вторую систему, т. е. вычисляют x.

Существенно, что для хранения ни y, ни x затрат памяти не требуется: их можно хранить там же, куда был введен вектор b.

Если A хранится по столбцам, то мы изменим алгоритм LU -разложения, как это показано на рис. 3.2. На k-м шаге измененного алгоритма сначала формируется k-й столбец матрицы L; это достигается векторной операцией деления. В самом внутреннем цикле (цикле по i) k-й столбец L, умноженный на число, вычитается из j-го столбца текущей матрицы A; длина столбцов равна n k. Таким образом, основной векторной операцией снова является триада, но теперь в качестве векторов выступают столбцы матрицы L и текущей матрицы A. В данный алгоритм также возможно внедрить любую из трех стратегий выбора главного элемента (см. подразд. 2.2).

3.2 Распараллеливание вычислений В этом разделе мы, следуя [8], излагаем некоторые понятия параллельных вычислений, которые в практике решения линейных систем имеют большое значение.

Параллельные вычисления реализуются не на обычных (скалярных) компьютерах, какими являются все персональные компьютеры, а на векторных или параллельных компьютерах. Их отличает то, что операндами команд копьютера являются не отдельные числовые величины (скаляры), а целые группы таких величин, объединяемых в векторы или матрицы. Поэтому векторно-матричные операции для своего выполнения требуют вызова всего 3 Векторно-ориентированные алгоритмы LU-разложения лишь одной команды. Выполнение таких команд начинается, как обычно, с загрузки операндов из памяти в векторно-матричный процессор и завершается обратным действием записью результата операции в память. В промежутке между этими действиями операции реализуются на аппаратном уровне в процессоре.

Векторные компьютеры. В основе таких компьютеров лежит концепция конвейеризации. Это означает явное сегментирование процессора на отдельные части (сегменты), каждая из которых выполняет свою вычислительную подзадачу независимо для соответствующих частей операндов.

Например, сумматор процессора для чисел с плавающей точкой разделен на шесть сегментов; каждый сегмент занят реализацией своей части операции сложения чисел. Всякий сегмент может работать только с одной парой операндов, а в целом на конвейере в текущий момент времени могут находиться шесть пар операндов. Преимущество подобной сегментации в том, что результаты выдаются в 6 раз быстрее (а в общем случае в K, где K число сегментов сумматора), чем в скалярном процессоре, который, получив пару операндов, не принимает новой пары, пока не вычислит результат для первой пары. Для реализации этой возможности ускорения нужно подавать данные из памяти в процессор достаточно быстро, чтобы конвейер был все время загружен данными и работой.

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

Распараллеливание. Независимо от того, на какой аппаратуре реализуется тот или иной вычислительный алгоритм, он обладает собственной, ему присущей характеристикой, показывающей возможности его распараллеливания.

Определение 3.2. Степенью параллелизма численной задачи называется число ее операций, которые можно выполнять параллельно.

Пример 3.1. Пусть требуется сложить два n-мерных вектора a и b.

Сложения их элементов независимы и потому могут выполняться параллельно. Степень параллелизма этого алгоритма равна n.

Пример 3.2. Пусть требуется сложить n чисел a1,..., an. Обычный последовательный алгоритм не пригоден для параллельных вычислений. Однако в самой задаче заключен немалый параллелизм. Можно разбить операнды на двойки, т. е. складывать их по двое на каждом этапе операции. Полностью эффект этой идеи проявляется, когда число операндов равно степени двойки, т. е. n = 2q. Если, например, q = 3, то все сложение займет q = 3 этапа, на каждом этапе действия выполняются параллельно, как показано на рис. 3.3.

Рис. 3.3. Сложение n чисел методом сдваивания для n = 8 [8] Очевидно, на первом этапе степень параллелизма равна n/2, на втором n/4 и т. д. В связи с этим приходим к обновленному определению.

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

3 Векторно-ориентированные алгоритмы LU-разложения Для приведенного примера 3.2 алгоритма сдваивания в задаче сложения n чисел средняя степень параллелизма равна тогда как в предыдущем примере 3.1 средняя степень параллелизма максимальна. Этот алгоритм (3.3) обладает идеальным параллелизмом, в то время как для алгоритма на рис. 3.3 средняя степень параллелизма в log n раз меньше идеальной.

3.3 Параллельное умножение матрицы на вектор где ai i-я строка матрицы A, а (ai, x) обычное скалярное произведение векторов ai и x. Каждое из m имеющихся здесь скалярных произведений, как известно, требует суммирования n поэлементных произведений aij xj.

Как показано в предыдущем подразделе, такое суммирование можно распараллеливать сдваиванием, но такой параллелизм вычисления каждого отдельного скалярного произведения так или иначе неидеален. Однако m скалярных произведений в (3.4) можно вычислять параллельно. Другой способ умножения матрицы на вектор дается формулой где aj теперь обозначает j-й столбец матрицы A.

Различие представлений (3.4) и (3.5) можно рассматривать как различие двух способов доступа к данным в памяти, что показывают две программы на рис. 3.4. Программа слева на рис. 3.4 реализует метод (3.4), тогда как программа справа реализует метод (3.5), и различие здесь только в порядке индексов для циклов. Алгоритм, основанный на представлении (3.5), записывается так:

Рис. 3.4. ij (слева) и ji (справа) формы матрично-векторного умножения [8] Как выше (в подразд. 3.1) говорилось, такая операция типа вектор плюс произведение вектора на число, называется триадой (или операцией saxpy);

некоторые векторные компьютеры выполняют ее особенно эффективно.

Сравнение приведенных способов умножения матрицы на вектор показывает, что на одних векторных компьютерах предпочтителен один способ, на других другой; многое определяется также и способом хранения данных в памяти. Предположим, что матрица A хранится по столбцам; такое соглашение в отношении двумерных массивов принято в Фортране. (В других языках, например в Паскале, двумерные массивы хранятся по строкам.) Тогда векторы, требуемые для алгоритма (3.5), располагаются в последовательно адресуемых ячейках памяти, в то время как для алгоритма (3.5) строки будут представлять векторы с шагом m. Однако в векторных компьютерах часто существует ограничение на доступ к векторам: в качестве операндов для векторных команд допускаются только векторы с шагом (т. е. такие, которые располагаются в последовательно адресуемых ячейках памяти). Поэтому, если матрица A хранится по столбцам, то эти соображения, связанные с памятью, усиливают аргументацию в пользу алгоритма (3.5). Если же матрица A хранится по строкам, то предпочтительней может оказаться алгоритм (3.4). Только детальный анализ может показать, какой выбор следует сделать для конкретной машины.

3.4 Параллельное LU -разложение Для распараллеленных вычислений нужны соответствующие параллельные или векторые компьютеры. С середины 70-х годов 20-го столетия фирма CRAY Research, Inc. производит векторные компьютеры, которые могут служить примером процессоров типа регистр–регистр. Под этим подразумевается, что существуют векторные команды, для которых операндами являются векторы. Эти команды получают свои операнды из очень быстрой памяти, именуемой векторными регистрами, и запоминают результаты опятьВекторно-ориентированные алгоритмы LU-разложения таки в векторных регистрах. Для операции сложения векторов это показано на рис. 3.5.

Рис. 3.5. Операция сложения в компьютере типа регистр–регистр [8] Предполагается, что каждый векторный регистр состоит из некоторого числа слов. Например, в машинах CRAY имеется восемь векторных регистров, каждый емкостью в 64 числа с плавающей точкой. До начала сложения операнды загружаются из оперативной памяти в регистры. После завершения сложения векторный результат переписывается из регистровой памяти в оперативную память. Для таких машин желателен иной подход к организации LU -разложения.

Исследуем вначале характер обменов во внутреннем цикле столбцового алгоритма LU -разложения на рис. 3.2. Для простоты предположим, что столбец матрицы A полностью вкладывается в векторный регистр, и начнем с рассмотрения случая, когда на фоне вычислений может выполняться только загрузка или только запись в память. Несколько первых операций указаны в следующем списке:

Сформировать первый столбец матрицы L.

Загрузить второй столбец матрицы A.

Модифицировать второй столбец матрицы A;

загрузить третий столбец матрицы A.

Модифицировать третий столбец матрицы A;

загрузить четвертый столбец матрицы A.

..................

Согласно (3.6), загрузка следующего столбца матрицы A совмещается с модификацией текущего столбца. Но затем возникает задержка при записи модифицированного второго столбца из регистра в память. Можно так модифицировать алгоритм, чтобы устранить задержку, вызванную записью в память (3.7). Идея состоит в том, чтобы выполнять необходимую обработку для j-го столбца полностью, прежде чем переходить к (j + 1)-му столбцу. При этом обработка каждого из остальных столбцов матрицы A откладывается до тех пор, пока не наступит время придать этому столбцу окончательный вид. Псевдокод данного алгоритма приведен на рис. 3.6.

Рис. 3.6. Столбцово ориентированная схема LU-разложения с отложенными модификациями (jki-алгоритм, см. с. 64) [8] Опишем несколько первых операций j-го шага вычислений, показывая таким образом характер обменов с памятью:

Заметим, что в алгоритме (3.9) не производится записей в память, пока вся работа с j-м столбцом матрицы A не завершена. Столбцы матрицы L все время должны загружаться в регистры, но эти загрузки идут на фоне вычислений. Только в начале и в конце каждого шага происходят задержки для загрузок и(или) записей. Вполне вероятно, что транслятор не сумеет распознать возможности оставить текущий j-й столбец в регистре; в этом случае результат, требуемый от алгоритма на рис. 3.6, либо достигается с переходом к программированию на языке ассемблера, либо аппроксимируется путем развертывания циклов. Еще одна потенциальная проблема при реализации данного алгоритма заключается в том, что длины векторов при 3 Векторно-ориентированные алгоритмы LU-разложения модификациях непостоянны: на j-м шаге мы модифицируем j-й столбец, используя n 1 последних элементов столбца 1, далее n 2 последних элементов столбца 2 и т. д.

Алгоритм с отложенными модификациями не столь нужен для тех машин типа регистр–регистр, в которых допускается совмещение с арифметикой как загрузок, так и записей в память. В этом случае операцию (3.7) можно было бы удалить, а операцию (3.8) заменить операцией Модифицировать третий столбец матрицы A;

Таким образом, запись в память второго столбца матрицы A происходит одновременно с загрузкой четвертого столбца.

Замечание 3.1. Материал подразд. 3.2, 3.3 и 3.4 из [8] приведен, чтобы объяснить те приложения, для которых создаются алгоритмы с отложенными модификациями: алгоритм на рис. 3.6 и другие, показанные ниже в подразд. 3.5. Таким образом, включение таких алгоритмов в лабораторную работу (проект) может рассматриваться как задача имитирования алгоритмов векторных или параллельных компьютеров на обычных (скалярных) компьютерах с целью освоения этих современных версий LU -разложения.

3.5 LU -разложение и его ijk-формы Ниже в описании ijk-алгоритмов факторизации (разложения), основанных на методе Гаусса исключения переменных, используем из [8] следующие обозначения для индексов:

k номер исключаемой переменной, i номер строки, т. е. модифицируемого уравнения, j номер столбца, т. е. коэффициента в модифицируемом уравнении.

Тогда общую основу всех алгоритмов удобно определить тройкой вложенных циклов вида Здесь последняя формула обозначает модификацию j-го элемента i-й строки матрицы A при исключении k-й переменной вектора неизвестных x из уравнений системы Ax = f. Перестановки трех индексов для циклов определяют 3! = 6 возможных вариантов алгоритмов, образуя так называемые ijk-формы, для каждого вида разложения. Для квадратной матрицы A размера (n n) возможны четыре вида разложения, а именно:

где черта сверху указывает на тот из сомножителей, который имеет единичную главную диагональ. Поэтому всего возможно построить 24 варианта ijk-алгоритмов разложения матрицы для решения различных задач: решения систем, обращения матрицы и вычисления ее определителя.

Рассмотрим все шесть ijk-форм для одного из четырех разложений (3.10), а именно, для LU -разложения матрицы A. Для численной иллюстрации возьмем следующий пример.

Пример 3.3.

Два алгоритма для LU -разложения матрицы A 1) kij-алгоритм, рис. 3.1.

Доступ к элементам матрицы A по строкам. Исключение по столбцам. Модификации немедДля j = k + 1 до n ленные. ГЭ любая из трех стратегий.

2) kji-алгоритм, рис. 3.2.

столбцам. Модификации немед- Для j = k + 1 до n стратегий.

3 Векторно-ориентированные алгоритмы LU-разложения Два алгоритма для LU -разложения матрицы A (столбцово ориентированные с отложенными модификациями) 3) jki-алгоритм, рис. 3.6. Для j = 2 до n A по столбцам. Исключение по ls,j1 = as,j1/aj1,j столбцам. Модификации отлопо (j 1)-му столбцу.

4) jik-алгоритм.

Доступ к элементам матрицы A по столбцам. Исключение по столбцам. Модификации отлоДля i = 2 до j женные. В цикле по s идет норДля k = 1 до i мировка (j 1)-го столбца. Перaij = aij lik akj.

вый цикл по i вычисляет столДля i = j + 1 до n бец для U, второй столбец для L. ГЭ столбцу.

Два алгоритма ijk-форм для LU -разложения матрицы A (строчно ориентированные с отложенными модификациями) 5) ikj-алгоритм.

Доступ к элементам матрицы A по строкам. Исключение по строкам. Модификации отлоДля j = k + 1 до n женные. ГЭ строке.

6) ijk-алгоритм.

Доступ к элементам матрицы A по строкам. Исключение по строкам. Модификации отлоДля k = 1 до j женные. Первый цикл по j наaij = aij lik akj ходит элементы i-й строки L.

Второй цикл по j элементы i-й строки U. ГЭ строке.

Рис. 3.7. Способ доступа к данным для kij-формы (слева) и для kji-формы (справа) LU-разложения. Обозначения: L, U вычисление закончено, обращений больше нет; главный элемент (ГЭ); деление на ГЭ (нормировка) [8] Рис. 3.8. Способ доступа к данным для jki-формы и для jik-формы (слева) и для ikjформы и для ijk-формы (справа) LU-разложения. Обозначения: L, U вычисление закончено, обращения больше не производятся; главный элемент (ГЭ);

деление на ГЭ (нормировка); обращений не было [8] Замечание 3.2. В приведенных алгоритмах не содержится процедура выбора главного элемента. Она дословно переносится из описания лабораторной работы № 1. Аналогичные алгоритмы могут быть написаны для остальных трех видов разложения матрицы A из списка (3.10). При написании программ, соответствующих приведенным алгоритмам, следует выполнить требование, согласно которому все вычисления выполняются в одном и том же двухмерном массиве, где сначала хранится матрица A. В процессе вычислений матрица A замещается элементами треугольных матриц, составляющих искомое разложение из списка (3.10). Способ доступа к данным для ijk-форм LU -разложения показан на рис. 3.7 и рис. 3.8. Расчеты по алгоритмам kij-формы и kji-формы LU -разложения достаточно очевидны. Для других четырех форм LU -разложения эти вычисления поясняются для примера 3.3 в табл. 3.1–3.4.

3 Векторно-ориентированные алгоритмы LU-разложения Таблица 3.1. Вычисления по алгоритму jki-формы для примера 3.3. Позиции ГЭ (без их реального выбора) показаны выделенным шрифтом Таблица 3.2. Вычисления по алгоритму jik-формы для примера 3.3. Позиции ГЭ (без их реального выбора) показаны выделенным шрифтом Таблица 3.3. Вычисления по алгоритму ikj-формы для примера 3.3. Позиции ГЭ (без их реального выбора) показаны выделенным шрифтом 3.6 Треугольные системы По окончании этапа приведения в гауссовом исключении нам необходимо решить треугольную систему уравнений Обычный алгоритм обратной подстановки описывается формулами Рассмотрим, как он может быть реализован в векторных операциях. Если U хранится по строкам (так будет, если на этапе приведения A хранилась по строкам), то формулы (3.11) задают скалярные произведения с длинами векторов, меняющимися от 1 до n1, и n скалярных делений (рис. 3.9 слева).

Альтернативный алгоритм, полезный, если U хранится по столбцам, представлен в виде псевдокода на рис. 3.9 справа. Он называется столбцовым алгоритмом (или алгоритмом векторных сумм). Как только найдено 3 Векторно-ориентированные алгоритмы LU-разложения Таблица 3.4. Вычисления по алгоритму ijk-формы для примера 3.3. Позиции ГЭ (без их реального выбора) показаны выделенным шрифтом Рис. 3.9. Алгоритмы скалярных произведений (слева) и столбцовый для обратной подстановки (справа) значение xn, вычисляются и вычитаются из соответствующих элементов ci величины произведений xn uin (i=1,...,n 1); таким образом, вклад, вносимый xn в прочие компоненты решения, реализуется до перехода к следующему шагу. Шаг с номером i состоит из скалярного деления, сопровождаемого триадой длины i1 (подразумевается,что шаги нумеруются в обратном порядке: n, n 1,..., 2, 1). Какой из двух алгоритмов выбрать, диктуется способом хранения матрицы U, если он был определен LU -разложением.

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

3.7 Задание на лабораторный проект № Написать и отладить программу, реализующую ваш вариант метода исключения с выбором главного элемента, для численного решения систем линейных алгебраических уравнений Ax = f, вычисления det A и A1.

Предусмотреть сообщения, предупреждающие о невозможности решения указанных задач с заданной матрицей A.

Отделить следующие основные части программы:

а) подпрограмму факторизации матрицы A, отвечающую вашему варианту метода исключения;

б) подпрограмму решения систем линейных алгебраических уравнений;

в) подпрограмму вычисления определителя матриц;

г) подпрограммы обращения матриц;

д) сервисные подпрограммы.

3 Векторно-ориентированные алгоритмы LU-разложения Уделить особое внимание эффективности программы (в смысле экономии оперативной памяти). Предусмотреть пошаговое выполнение алгоритма исключения с выводом результата на экран.

Выполнить следующие пункты задания.

1. Провести подсчет фактического числа выполняемых операций умножения и деления при решении системы линейных алгебраических уравнений, сравнить его с оценочным числом (n3/3).

2. Определить скорость решения задач (решение систем линейных алгебраических уравнений, обращение матриц) с учетом времени, затрачиваемого на разложение матрицы. Для этого спроектировать и провести эксперимент, который охватывает матрицы порядка от 5 до 100 (через 5 порядков). Представить результаты в виде таблицы и графика зависимости времени выполнения (в минутах и секундах) от порядка матриц. Таблицу и график вывести на экран.

3. Оценить точность решения систем линейных алгебраических уравнений, имеющих тот же самый порядок, что и задачи из пункта 2. Для этого сгенерировать случайные матрицы A, задать точное решение x и образовать правые части f = Ax. Провести анализ точности вычисленного решения x от порядка матрицы. Результаты представить в виде таблицы и графика.

Для заполнения матрицы A использовать случайные числа из диапазона от 100 до 100. В качестве точного решения взять вектор x = (1, 2,..., n)T, где n порядок матрицы. Для оценки точности использовать норму вектора 4. Повторить пункт 3 задания для плохо обусловленных матриц (см. подразд. 2.6), имеющих порядок от 4 до 40 с шагом 4.

5. Вычислить матрицу A1 следующими двумя способами.

Способ 1 через решение системы AX = I, где I единичная матрица.

Способ 2 через разложение матрицы A в произведение элементарных матриц, обращение которых осуществляется аналитически, а их произведение дает матрицу A1.

Сравнить затраты машинного времени и точность обращения матриц при использовании указанных способов 1 и 2. Эксперименты провести для случайных матриц порядков от 5 до 100 через 5. Для оценки точности в обоих способах использовать оценочную формулу В этом выражении норму матрицы вычислять в соответствии со следующим определением:

чение, полученное в результате обращения каждым из способов 1 и 2.

6. Провести подсчет фактического числа выполняемых операций умножения и деления при обращении матриц первым и вторым способами, сравнить его с оценочным числом (n3).

Замечание 3.3. По ходу проведения численных экспериментов на экран дисплея должны выводиться следующие таблицы.

Решение систем линейных алгебраических уравнений:

Аналогичная таблица должна быть построена для плохо обусловленных матриц.

Порядок Замечание 3.4. Результаты экспериментов необходимо вывести на экран в форме следующих графиков.

Графики решения систем линейных алгебраических уравнений:

зависимость реального и расчетного числа операций от порядка матрицы (для разных графиков использовать разные цвета);

зависимости времени и точности решения от порядка матриц.

зависимость реального и оценочного числа операций от порядка матрицы (для разных графиков использовать разные цвета);

зависимости времени и точности обращения первым и вторым способом от порядка матриц.

3 Векторно-ориентированные алгоритмы LU-разложения Таблица 3.5. Варианты задания на лабораторный проект № выбор ГЭ по столбцу активной подматрицы выбор ГЭ по строке активной подматрицы 3.8 Варианты задания на лабораторный проект № В табл. 3.5 приведены 40 номеров вариантов задания на лабораторную работу (проект) № 2 с тремя стратегиями выбора главного элемента.

Если нет других указаний преподавателя, выбирайте ваш вариант по вашему номеру в журнале студенческой группы.

Алгоритмы окаймления в LU -разложении 4.1 Метод окаймления Хотя ijk-формы дают шесть различных способов организации LU -разложения, имеются и другие способы, потенциально полезные для векторных компьютеров. Даже тогда, когда та или иная ijk-форма теоретически пригодна для конкретной векторной машины, при ее реализации могут возникнуть проблемы, особенно если применяется язык высокого уровня. Разбираемые ниже способы организации вычислений основаны на операциях с подматрицами; потенциально они проще реализуются и облегчают написание переносимых программ.

В основе этих способов организации лежит идея окаймления [14]. Математически ее можно представить следующим образом. Разобьем матрицу A на блоки и, соответственно, разобьем на блоки сомножители L и U искомого разложения LU = A:

Здесь lT, uT, aT и aT векторы-строки, а l3j, u1j, a1j и a3j векторыj1 j3 j1 j столбцы; каждый из этих элементов находится на j-й позиции.

4.2 Окаймление известной части разложения Пусть известно разложение L11U11 = A11, которое можно рассматривать как равенство (4.1) для блока A11. Запишем аналогичные равенства для тех 4 Алгоритмы окаймления в LU-разложении трех блоков, которые окаймляют эту известную часть разложения, следуя правилу перемножения блок-матриц, а именно, для aT, a1j и ajj :

Из первого уравнения (4.2), переписанного в виде U11lj1 = aj1, находим lj1, из второго находим u1j и затем из третьего находим ujj = ajj lT u1j.

При этом первое и второе уравнения описываются следующими нижнетреугольными системами Существуют два естественных варианта реализации окаймления известной части LU -разложения.

В первом варианте треугольные системы (4.3) решаются с помощью столбцового алгоритма, во втором с помощью алгоритма скалярных произведений. Псевдокоды этих двух вариантов приведены на рис. 4.1.

Рис. 4.1. Алгоритмы окаймления известной части LU-разложения: столбцовый (слева) и алгоритм скалярных произведений (справа) В первом цикле по i на рис. 4.1 (слева) выполняется модификация j-го столбца матрицы A и тем самым вычисляется j-й столбец матрицы U. Во втором цикле по i модифицируется j-я строка матрицы A и вычисляется j-я строка матрицы L. Заметим, что при i = j во втором цикле по i пересчитывается элемент (j, j) матрицы A; в результате, согласно (4.2), получается элемент ujj.

Во второй форме алгоритма окаймления на рис. 4.1 (справа) первый цикл по i,k вычисляет j-й столбец матрицы U, для чего из элементов aij вычитаются скалярные произведения строк с 2-й по (j 1)-ю матрицы L с j-м столбцом U. Это эквивалентно решению системы L11u1j = a1j. Во втором цикле по i,k модифицируется j-я строка A путем делений (нормировок) элементов этой строки, сопровождаемых опять-таки вычитаниями скалярных произведений j-й строки L и столбцов U. Это эквивалентно решению треT угольной системы U11lj1 = aj1 относительно j-й строки матрицы L. Отметим, что здесь при j = i модифицируется элемент (j, j) матрицы A, и это относится уже к вычислению j-го столбца матрицы U ; в результате получается элемент ujj. Вычисления по этим формам показаны в табл. 4.1.

Таблица 4.1. Вычисления по алгоритмам на рис. 4.1 для примера 3.3. Позицииэлемента–делителя столбца L показаны выделенным шрифтом В обеих формах окаймления обращения к данным производятся одинаково, что показано на рис. 4.2.

Рис. 4.2. Доступ к данным в алгоритмах окаймления известной части разложения.

вычисление закончено, но обращения происходят. A обращений не было.

Вычисляются: j-й столбец матрицы U и j-я строка матрицы L Обратим внимание, что в обоих случаях требуется доступ и к строкам, и к столбцам матрицы A. Поэтому алгоритмы будут неэффективны для векторных компьютеров, требующих, чтобы элементы вектора находились в смежных позициях памяти. Еще одной сложностью является внедрение процедуры выбора главного элемента в эти алгоритмы.

4 Алгоритмы окаймления в LU-разложении 4.3 Окаймление неизвестной части разложения Основная работа в алгоритмах окаймления приходится на решение треугольных систем (4.3). Это матрично-векторные операции, которые можно реализовать в виде подпрограмм по типу рис. 4.1, добиваясь в них максимальной для данной машины эффективности. Еще один способ организации вычислений, который называют алгоритмом Донгарры–Айзенштата, имеет то преимущество, что его основной операцией является матричновекторное умножение. Математически алгоритм можно описать следующим образом. Выпишем из равенства (4.1) три других соотношения, на этот раз для ajj, a3j и aT. Отсюда получим Характер доступа к данным при таком вычислении показан на рис. 4.3.

Рис. 4.3. Доступ к данным в алгоритмах окаймления неизвестной части разложения.

L11, U11 вычисление закончено, обращений больше нет. L31, U13 вычисление закончено, но обращения происходят. A33 обращений не было. Вычисляются: j-й Видно, что блоки U13 и L31, необходимые для вычислений (4.4), на каждый такой момент времени уже известны, так же как и все другие величины в правых частях равенств (4.4), поэтому здесь нет решения уравнений.

Основной операцией в (4.4) является умножение вектора на прямоугольную матрицу. Можно реализовать такие умножения посредством скалярных произведений или линейных комбинаций, что приводит к двум различным формам алгоритма, показанным на рис. 4.4.

Рис. 4.4. Алгоритмы Донгарры–Айзенштата окаймления неизвестной части LUразложения: алгоритм линейных комбинаций (слева) и алгоритм скалярных произведений (справа) Первый цикл по k,i на рис. 4.4 (слева) производит последовательные модификации j-й строки матрицы A, которая по окончании цикла k превращается в j-ю строку матрицы U. Эти модификации можно рассматривать как вычитание векторно-матричного произведения lT U13 из aj3 во второй формуле uj3 = aj3 lj1 U13 в (4.4) c помощью линейных комбинаций строк U. В случае j = i результатом модификации будет первая величина ujj в (4.4). Во второй паре циклов по k и i выполняются модификации j-го столбца матрицы A по формуле l3j = = (a3j L31u1j ), т. е. по второй формуле (4.4) с точностью до деления на ujj c вычислением матрично-векторного произведения L31u1j в (4.4) посредством линейных операций столбцов матрицы L. Обратите внимание, в отличие от алгоритма отложенных модификаций на рис. 3.6, теперь длины векторов, участвующих в линейных комбинациях, одинаковы. Второй оператор цикла с индексом k можно удалить, причем программа снова будет верна; мы вставили этот оператор, чтобы подчеркнуть наличие линейных комбинаций. Отметим еще, что в первом цикле по k,i происходит обращение к строкам матрицы A, а во втором цикле по k,i к ее столбцам. Следовательно, эта форма неэффективна для векторных компьютеров, требующих размещения элементов вектора в смежных ячейках памяти.



Pages:     || 2 | 3 | 4 | 5 |


Похожие работы:

«Е.В. ГЛЕБОВА, Л.С. ГЛЕБОВ, Н.Н. САЖИНА ОСНОВЫ РЕСУРСО-ЭНЕРГОСБЕРЕГАЮЩИХ ТЕХНОЛОГИЙ УГЛЕВОДОРОДНОГО СЫРЬЯ Допущено Учебно-методическим объединением вузов Российской Федерации по нефтегазовому образованию в качестве учебного пособия для подготовки бакалавров и магистров по направлению 553600 Нефтегазовое дело Издательство Нефть и газ РГУ нефти и газа им. И.М. Губкина Москва PDF created with pdfFactory trial version www.pdffactory.com УДК 662. Глебова Е.В., Глебов Л.С., Сажина Н.Н. Основы...»

«Тверское библиотечное общество Краеведческие исследования библиотек Тверские библиотечные чтения 2008 года Тверь 2009 ББК78.3 К78 Составители и редакторы: Л.А. Абрамова, заведующая научно-методическим отделом Тверской областной универсальной научной библиотеки им. А.М. Горького Т.А. Ильина, зав. сектором Научной библиотеки Тверского государственного университета Краеведческие исследования библиотек : тверские библиотечные чтения 2008 года / Твер. библ. о-во. – Тверь, 2009. – 113 с. Статьи...»

«МИНИСТЕРСТВО ЗДРАВООХРАНЕНИЯ РЕСПУБЛИКИ УЗБЕКИСТАН НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ФТИЗИАТРИИ И ПУЛЬМОНОЛОГИИ им. Ш.А.АЛИМОВА ХИРУРГИЧЕСКОЕ ЛЕЧЕНИЕ ПРОГРЕССИРУЮЩЕГО И ОСЛОЖНЕННОГО ФИБРОЗНО-КАВЕРНОЗНОГО ТУБЕРКУЛЕЗА ЛЕГКИХ (методические рекомендации) ТАШКЕНТ - 2003 МИНИСТЕРСТВО ЗДРАВАООХРАНЕНИЯ РЕСПУБЛИКИ УЗБЕКИСТАН “УТВЕРЖДАЮ” ПредседательУченого Медицинского Совета, академик АН РУз М.С.Абдуллаходжаева “_”2003 г. ХИРУРГИЧЕСКОЕ ЛЕЧЕНИЕ ПРОГРЕССИРУЮЩЕГО И ОСЛОЖНЕННОГО ФИБРОЗНО-КАВЕРНОЗНОГО...»

«Комплексная сексолого-психиатрическая экспертиза обвиняемых в многоэпизодных сексуальных правонарушениях: методические рекомендации, 2010, 20 страниц, 5860021283, 9785860021280, ГНЦССП, 2010. В работе рассмотрен алгоритм проведения комплексной сексолого-психиатрической экспертизы обвиняемых в многоэпизодных сексуальных правонарушениях Опубликовано: 7th June Комплексная сексолого-психиатрическая экспертиза обвиняемых в многоэпизодных сексуальных правонарушениях: методические рекомендации СКАЧАТЬ...»

«Негосударственное образовательное учреждение высшего профессионального образования Институт экономики и управления (г. Пятигорск) НОУ ВПО ИнЭУ УТВЕРЖДАЮ Проректор по учебной работе / И.В. Данильченко / (Протокол № 2 от 29 октября 2013 г.) МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО НАПИСАНИЮ КУРСОВЫХ РАБОТ ПО ДИСЦИПЛИНЕ Б3.Б.5 Проектирование информационных систем 230700.62 - Прикладная информатика Направление подготовки бакалавр Квалификация (степень) выпускника Прикладная информатика в экономике Профиль...»

«КУРС ПРАВА ЧЕЛОВЕКА УЧЕБНОЕ ПОСОБИЕ Москва 2012 УДК 341.231.141.14:343.211.3(470+571)(075.9) ББК 66.4(0)я77-1+67.412.1я77-1 К93 Издание осуществлено в рамках проекта Защита фундаментальных прав и правозащитников при финансовом содействии Дома Cвободы Составитель В. Карастелев Отв. редактор Н. Костенко Курс Права человека : учеб. пособие / [сост. В. Карастелев]. — М. : К93 Моск. Хельсинк. группа, 2012. — 124 с. : ил. — ISBN 5-98440-059-6. I. Карастелев, В., сост. В брошюре изложена современная...»

«Л.С. СаЛоматина Теория и практика обучения младших школьников созданию письменных текстов различных типов (повествование, описание, рассуждение) Лекции 1–4 москва Педагогический университет Первое сентября 2010 Лариса Сергеевна Саломатина материалы курса теория и практика обучения младших школьников созданию письменных текстов различных типов (повествование, описание, рассуждение): лекции 1–4. – м.: Педагогический университет Первое сентября, 2010. – 124 с. Учебно-методическое пособие Редактор...»

«Методическое объединение вузовских библиотек Алтайского края Вузовские библиотеки Алтайского края Сборник Выпуск 10 Барнаул 2010 ББК 78.34 (253.7)657.1 В 883 Редакционная коллегия: Л. В. Бобрицкая, И. Н. Кипа, Н. Г. Шелайкина, Е. А. Эдель, Т. А. Мозес Л. А. Божевольная. Гл. редактор: Н. Г. Шелайкина Отв. за выпуск: М. А. Куверина Компьютерный набор: Л. Н. Вагина Вузовские библиотеки Алтайского края: сборник: Вып. 10. /Метод. объединение вуз. библиотек Алт. края. – Барнаул: Изд-во АлтГТУ, 2010....»

«Областное государственное бюджетное образовательное учреждение Томский базовый медицинский колледж УТВЕРЖДАЮ Зам. директора по УВР Архипова Н.Ф. 2014 РАБОЧАЯ ПРОГРАММА ПРОИЗВОДСТВЕННОЙ ПРАКТИКИ (ПРЕДДИПЛОМНОЙ) Специальность 060102. Акушерское дело Томск 2014 Рабочая программа производственной практики (преддипломной) разработана на основе Федерального государственного образовательного стандарта (далее ФГОС) по специальностям среднего профессионального образования (далее СПО): 060102....»

«СОДЕРЖАНИЕ 1. Общие положения 1.1. Определение основной образовательной программы (ООП) бакалавриата 1.2.Обоснование выбора направления и профиля подготовки 1.3. Нормативные документы для разработки ООП бакалавриата 1.4. Общая характеристика вузовской основной образовательной программы высшего профессионального образования (бакалавриат) 1.5. Требования к абитуриенту 2. Характеристика профессиональной деятельности выпускника ООП бакалавриата 2.1. Область профессиональной деятельности выпускника...»

«Министерство образования и науки Российской Федерации Нижегородский государственный педагогический университет Т.А. Иванова, Н.А. Серова Выпускная квалификационная работа по теории и методике обучения математике Учебно-методическое пособие Нижний Новгород 2006 Печатается по решению редакционно-издательского совета Нижегородского государственного педагогического университета Иванова Т.А., Серова Н.А. Выпускная квалификационная работа по теории и методике обучения математике: Учебно-методическое...»

«by УДК 677.024.1(07) Составитель: доц. Медвецкий С.С. МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ tu. УО ВИТЕБСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ vs РЕКОМЕНДОВАНО УТВЕРЖДАЮ редакционно-издательским Первый проректор УО ВГТУ советом УО ВГТУ _ В.В. Пятов _ С.И. Малашенков in. _ 2008 г. 2008 г. lsp Ткацкое производство : методическое указание к лабораторным работам по теме Узлы и механизмы ткацкого станка для студентов специальности 1-53 01 01 – 05 Автоматизация /be технологических...»

«СМОЛЕНСКИЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ Елисеева И.Н. СОДЕРЖАНИЕ И МЕТОДИКА СОЦИАЛЬНО-МЕДИЦИНСКОЙ Р АБОТЫ Учебно-методическое пособие (для студентов заочной формы обучения, обучающихся по специальности 040101 (350500) Социальная работа) Смоленск, 2008 СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ Программа содержит три раздела: Раздел 1. Теоретические основы социально-медицинской работы. Раздел 2. Содержание и методика социально-медицинской работы в учреждениях разного типа. Раздел 3. Особенности...»

«2 3 СРУКТУРА ПРОГРАММЫ Пояснительная записка Программа, темы семинарских занятий и методические указания по дисциплине Отечественная история составлены в соответствии с требованиями (федеральный компонент) государственного стандарта второго поколения в области профессионального высшего образования, обязательного минимума содержания и уровня подготовки специалистов по циклу Общие гуманитарные и социально-экономические дисциплины. Курс Отечественная история в вузе базируется на знаниях,...»

«С.И. КОРЯГИН И.В. ПИМЕНОВ, В.К. ХУДЯКОВ СПОСОБЫ ОБРАБОТКИ МАТЕРИАЛОВ Калининград 2000 3 С.И. КОРЯГИН И.В. ПИМЕНОВ, В.К. ХУДЯКОВ СПОСОБЫ ОБРАБОТКИ МАТЕРИАЛОВ Рекомендовано Министерством образования Российской Федерации в качестве учебного пособия для студентов высших учебных заведений технических специальностей Калининград 2000 4 УДК 678.5.046.364 Корягин С.И., Пименов И.В., Худяков В.К. Способы обработки материалов: Учебное пособие / Калинингр. ун-т – Калининград, 2000. – 448 с. – ISBN...»

«1 МИНИСТЕРСТВО Государственное РОССИЙСКИЙ ОБРАЗОВАНИЯ И бюджетное образователь- ГОСУДАРСТВЕННЫЙ НАУКИ РОССИЙСКОЙ ное ГУМАНИТАРНЫЙ ФЕДЕРАЦИИ учреждение высшего УНИВЕРСИТЕТ профессионального ФИЛИАЛ В Г. БАЛАШИобразования ХЕ Кафедра экономико-управленческих и правовых дисциплин Филиала РГГУ в городе Балашихе ТЕРРИТОРИАЛЬНАЯ ОРГАНИЗАЦИЯ НАСЕЛЕНИЯ Учебно-методический комплекс для студентов очного отделения Для специальности 080504 - государственное и муниципальное управление Квалификация 65 -...»

«В ПОМОЩЬ ШКОЛЬНОМУ УЧИТЕЛЮ Е. Н. СОРОКИНА ПОУРОЧНЫЕ РАЗРАБОТКИ ПО ОБЩЕСТВОЗНАНИЮ ПРОФИЛЬНЫЙ УРОВЕНЬ 11 класс МОСКВА • ВАКО • 2009 ТОЛЬКО для ОЗНАКОМЛЕНИЯ www.moimirknig.com для www.mirknig.com УДК 372.83 ББК 74.266 С14 Сорокина Е.Н. С14 Поурочные разработки по обществознанию. Профиль­ ный уровень: 11 класс. - М.: ВАКО, 2009. - 272 с. - (В по­ мощь школьному учителю). ISBN 978-5-94665-891-1 Пособие представляет собой поурочные разработки по общест­ вознанию для 11 класса по учебнику под...»

«Федеральное агентство по образованию Филиал сочинского государственного университета туризма и курортного дела в г. Н. Новгород Факультет адаптивной физической культуры Кафедра реабилитологии Каулина Е.М. СРЕДСТВА, ФОРМЫ, МЕТОДЫ ЛЕЧЕБНОЙ ФИЗИЧЕСКОЙ КУЛЬТУРЫ В РЕАБИЛИТАЦИИ ЛИЦ С ОТКЛОНЕНИЯМИ В СОСТОЯНИИ ЗДОРОВЬЯ Учебное пособие Для студентов всех форм обучения специальности Физическая культура для лиц с отклонениями в состоянии здоровья (Адаптивная физическая культура) Нижний Новгород ББК 53. К...»

«НОУ ВПО ИВЭСЭП НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ИНСТИТУТ ВНЕШНЕЭКОНОМИЧЕСКИХ СВЯЗЕЙ, ЭКОНОМИКИ И ПРАВА КОНСТИТУЦИОННОЕ ПРАВО ЗАРУБЕЖНЫХ СТРАН УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по специальности 030501.65 Юриспруденция САНКТ-ПЕТЕРБУРГ 2011 Конституционное право зарубежных стран: Учебно-методический комплекс / Авт.-сост. А.В.Фомичёв. - СПб.: ИВЭСЭП, БК 67. И Учебно-методический комплекс /Авт.-сост. А.В.Фомичёв - СПб.: ИВЭСЭП, 2011....»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования ШУЙСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра теории и методики физической культуры и спорта УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по дисциплине АНАТОМИЯ И ФИЗИОЛОГИЯ РЕБЕНКА для специальности 050720.65 - Физическая культура со специализацией Физическое воспитание в дошкольных учреждениях Составитель: Воробушкова М.В., доктор медицинских наук, профессор Шуя,...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.