Программная реализация метода отражений на языке программирования Pascal




Скачать 336.48 Kb.
НазваниеПрограммная реализация метода отражений на языке программирования Pascal
страница1/4
Дата публикации15.03.2013
Размер336.48 Kb.
ТипДокументы
vbibl.ru > Математика > Документы
  1   2   3   4
Содержание
Вступление…………………………………………………...3

Раздел 1. Теоретические основы метода отражений (Хаусхолдера) для решения СЛАУ………………...5

1.1. Суть метода отражений для решения СЛАУ…..5

1.2. Модификации метода Хаусхолдера……………..10

1.3. Рамки использования метода отражений для решения СЛАУ………………………..…………18

Раздел 2. Программная реализация метода отражений

на языке программирования Pascal………...……24

2.1. Программный код решения СЛАУ методом отражений………………………………………24

2.2. Документация программы и ее характеристика………………………………...29

Раздел 3. Заключительные положения работы………..30

3.1. Сравнение метода отражений с остальными методами решения СЛАУ……………………...30

3.2. Перспективы программы и возможность ее модификации…………………………………….37

Заключение…………………………………………………39

Список использованной литературы…………………...41

Приложения………………………………………………...48

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

Каждая такая система уравнений должна иметь свое решение (кроме некоторых частных случаев). В современной математике уже есть много способов решения систем уравнений. Например, такие методы: наименьших квадратов, вращения, отражения, главных элементов, исключения, итераций, Гаусса, Зейделя, Якоби, Холецкого, Ланцоша и т.п. Кроме того, каждый из этих методов имеет свои модификации, развившиеся при усовершенствовании метода и расширении его области применения.

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

Целью работы выступает описание и глубокий анализ самого метода отражений и его модификаций на примере решения нескольких видов СЛАУ.

На основании поставленной цели формируются и задачи курсового проекта:

  1. Провести теоретическое описание метода отражений и его модификаций (Раздел 1);

  2. Построить алгоритмы программы, составить программный код метода отражений и провести анализ работы этой программы (Раздел 2);

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

  4. Провести сравнительный анализ всех методов решения СЛАУ и очертить границы их использования (Раздел 3).

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

Раздел 1. Теоретические основы метода отражений (Хаусхолдера) для решения СЛАУ.
1.1. Суть метода отражений для решения СЛАУ (метод Хаусхолдера).
Алгоритм Хаусхолдера приводит симметричную матрицу A размером (n x n) к трехдиагональной форме за (n - 2) ортогональных преобразований. Каждое преобразование уничтожает требуемую часть целой строки и целого соответствующего столбца. Базовой матрицей является матрица Хаусхолдера P, имеющая форму

P = 1 - 2wwT,

где w -- действительный вектор такой что |w|2 = 1. (В обозначениях, принятых здесь, матричное, или диадное, произведение векторов a и b записывается как abT, в то время как скалярное произведение этих векторов aTb). Матрица P является ортогональной, поскольку

P2 = (1 - 2wwT)(1 - 2wwT) = 1 - 4wwT + 4w(wTw)wT = 1.

Таким образом, P = P-1. Но PT = P, следовательно PT = P-1, что и доказывает ортогональность.

Перепишем P как

P = 1 - (uuT)/H,   где  H = |u|2/2,

и теперь u может быть любым вектором. Пусть x -- вектор, составленный из первого столбца матрицы A. Выберем

u = x - s|x|e1,

где e1 -- единичный вектор [1, 0,...,0]T, s -- либо 1, либо -1, а выбор знака s будет сделан позже. Тогда

Px = x - (u(x - s|x|e1)Tx)/H = x - (2u(|x|2 - s|x|x1))/(2|x|2 - 2s|x|x1) = x - u = s|x|e1.

Это показывает, что матрица Хаусхолдера P действует на заданный вектор x, уничтожая все его элементы, кроме первого. [15]

Для приведения симметричной матрицы ^ A к трехдиагональной форме, вектор x, который будет образовывать первую матрицу Хаусхолдера, составим из нижних n - 1 элементов первого столбца. Тогда будут обнулены нижние n - 2 элемента:

 

Здесь матрицы записаны в блочной форме, причем (n-1)P1 обозначает матрицу Хаусхолдера размерами ((n-1) x (n-1)). Величина k это просто плюс или минус модуль вектора [a21, ..., an1]T.

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

Здесь был использован факт, что PT = P.

Для второй трансформации матрица Хаусхолдера составляется на основе нижних (n - 2) элементов второго столбца, и из нее конструируется матрица преобразования:



Единичный блок в левом верхнем углу обеспечивает сохранение трехдиагональности, полученной на предыдущей стадии, в то время как матрица Хаусхолдера (n-2)P2 размера (n-2) добавляет еще один столбец и строку к трехдиагональному результату. Ясно, что цепочка (n-2) таких преобразований приведет матрицу A к трехдиагональному виду.

Вместо того, чтобы явно проводить матричные умножения в выражениях PAP, мы вычислим вектор

p = (Au)/H.

Тогда

AP = A(1 - (uuT)/H) = A - puT,   A' = PAP = A - puT - upT + 2KuuT,

где скаляр K определяется как:

K = (uTp)/(2H).

Если мы обозначим

q = p - Ku,

то будем иметь

A' = A - quT - uqT.

Последняя формула удобна для вычислений.

Программа редукции Хаусхолдера, основанная на алгоритме из [15] и помещенная ниже, реально начинает действие с n-ого столбца матрицы A, а не с первого, как было написано выше. В деталях алгоритм выглядит следующим образом. На стадии m (m = 1, 2, ..., n-2) вектор u имеет вид:

u = [ai1, ai2, ..., ai,i-2, ai,i-1 + , 0, ..., 0].

Здесь

i = n - m + 1 = n, n-1, ..., 3.

Величина  (что соответствует s|x| в прежних обозначениях) определяется как

2 = (ai1)2 + ... + (ai,i-1)2.

Знак  выбирается так, чтобы совпадать со знаком ai,i-1 для уменьшения ошибки округления.

Переменные вычисляются в следующем порядке: , u, H, p, K, q, A'. На каждой m-ой стадии матрица A становится трехдиагональной в последних m - 1 строках и столбцах.

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

Q = P1P2...Pn-2

на матрицу этих векторов. Произведение трансформирующих матриц Q формируется рекурсией после нахождения всех Pi:

Qn-2 = Pn-2, ..., Qj = PjQj+1, ..., Q = Q1.

На входе программы задается действительная симметричная матрица в массиве a[1...n][1...n]. На выходе этот массив содержит элементы матрицы Q. Вектор d[1...n] содержит множество диагональных элементов A', вектор e[1...n] содержит внедиагональные элементы A', начиная с e[2]. Заметим, что поскольку исходное содержимое массива a уничтожается, то при производстве серии последовательных вычислений с A он должен быть скопирован перед передачей в программу.

Промежуточные результаты не требуют дополнительной памяти. На стадии m вектора p и q не равны нулю только для элементов с индексами 1 ... i (вспомним, что i = n - m + 1), а вектор u -- только для элементов с индексами 1 ... i - 1. Элементы вектора e определяются в порядке n, n - 1, ..., так что вектор p можно держать на месте неопределенных элементов e. Вектор q может записываться поверх p, так как после определения q вектор p уже не требуется. Вектор u размещается в i-ой строке массива a, а u/H -- в i-ом столбце. После проведения редукции, матрицы Qj вычисляются с использованием записанных в массив a векторов u и u/H. Поскольку матрица Qj является единичной для последних n - j + 1 строк и столбцов, то требуется вычислить ее элементы лишь до строки и столбца n - j. При этом можно перезаписать u и u/H в соответствующих строке и столбце, поскольку они более не нужны.

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

2 < (наименьшее представимое число)/(машинная точность)

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

 = k=1i-1(|aik|).

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

aik --> aik/

и проводим преобразование с масштабированными величинами. (Преобразование Хаусхолдера зависит только от отношения элементов).

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



Интервальный метод Хаусхолдера для комплексных линейных систем.

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

Введение

Исследуется интервальная система линейных алгебраических уравнений (ИСЛАУ)



где элементами nхn-матрицы A и n-вектора правой части b являются ком­плексные интервалы.

Множество решений ИСЛАУ в общем случае не имеет простого описания. Поэтому мы ограничимся нахождением интервального вектора, целиком содер­жащего это множество решений. Как известно, полученный вектор называется внешней оценкой множества решений ИСЛАУ.

Одним из способов нахождения внешней оценки множества решений ИС­ЛАУ является метод Хаусхолдера [1], его вещественный вариант известен так­же в отечественной литературе как метод отражений [2, 3]. Суть этого метода заключается в том, что матрица системы A приводится к верхней треуголь­ной форме с помощью последовательности ортогональных преобразований. В отличие от метода Гаусса решения ИСЛАУ [4], метод Хаусхолдера дает более узкие внешние оценки множеств решений, если интервалы в матрице и правой части "не слишком широки". Кроме того, интервальный метод Хаусхолдера поз­воляет получать ответ в тех задачах, к которым интервальный метод Гаусса неприменим.

Отметим, что метод Хаусхолдера ранее применялся для внешнего оцени­вания множеств решений ИСЛАУ с вещественными интервальными парамет­рами. Целью работы является обобщение метода Хаусхолдера на случай ком­плексных ИСЛАУ.

Чтобы сделать изложение нашей работы самодостаточным, мы подробно описываем множество комплексных интервалов и основные свойства арифме­тик комплексных интервалов.

Обозначения:

  • – множество вещественных чисел,

– множество комплексных чисел,

  • – множество замкнутых интервалов на ,

  • — множество комплексных интервалов,

  • — множество n-мерных векторов с элементами из

– множество -матриц с элементами из

  1. ^ Комплексные интервальные арифметики

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

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

1.1.1. Прямоугольники в качестве комплексных интервалов Определение 1. Множество



называется прямоугольным комплексным интервалом.

Множество всех таких комплексных интервалов обозначим через

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

где

а каждый элемент — как сумму



откуда видно, что .

Элементы и из считаются равными, если



Определенное здесь отношение равенства рефлексивно, симметрично и транзитивно.

Теперь обобщим вещественную интервальную арифметику на комплексный случай.
  1   2   3   4

Добавить документ в свой блог или на сайт

Похожие:

Программная реализация метода отражений на языке программирования Pascal iconКонспект урока Основы программирования на языке Pascal Структура программы
Программа на языке Паскаль состоит из заголовка, разделов описаний и раздела операторов. Заголовок программы содержит имя программы,...

Программная реализация метода отражений на языке программирования Pascal icon«Разработка приложения с графическим интерфейсом на языке программирования...
В качестве курсовой работы по программированию предлагается реализация игры «Виселица». Приложение должно быть реализовано на языке...

Программная реализация метода отражений на языке программирования Pascal iconРабочая программа по курсу «основы Программирования на языке ассемблер»
Программа предназначена для обучения основам программирования на языке низкого уровня Ассемблере учащихся средних школ, учреждений...

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

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

Программная реализация метода отражений на языке программирования Pascal iconРуководство пользователя 7 1 Меню «Файл»
Программная реализация алгоритмов кодирования и декодирования для бчх-кодов и кодов Рида-Маллера

Программная реализация метода отражений на языке программирования Pascal iconПоляков Д. Б., Круглов И. Ю. Программирование в среде турбо паскаль (версия 5)
Зуев Е. А. Программирование на языке turbo pascal 0, М.: Радио и связь, 1993. 384

Программная реализация метода отражений на языке программирования Pascal iconПрограмма кружка «основы программирования на примере pascal»
Количество часов: 68 (10 часов теоретические занятия, 35 часов практические занятия, 23 часа проектная работа)

Программная реализация метода отражений на языке программирования Pascal iconФункциональное тестирование Цель работы
Программная реализация тестов, производящих функциональное тестирование алгоритма пирамидальной сортировки из курса лабораторных...

Программная реализация метода отражений на языке программирования Pascal iconИнтеграционное тестирование Цель работы
Программная реализация тестов, производящих интеграционное тестирование алгоритма пирамидальной сортировки из курса лабораторных...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница