Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод исключения Гаусса




Прямые (точные) методы

Computational modeling. Criticisms of psychology.

Psychological and Drug Treatments

Depression

Mental Health

Affiliation

Color Psychology

Sleep

Motivation

Thinking As a Process of Cognition

Social Pressure and Perception

Perception and Imagery

Careers in Psychology

How Psychologists Study the Mind

Conceptual Approaches to Psychology

Psycology as a Science

Organization of the Nervous System

How the Brain is Studied?

What is Psychology?

What is the Difference between Psychologist and Psychiatrist?

What is Clinical Psychology?

Secrets of the Brain: the Mystery of Memory

What is Stress?

What is Social Phobia?

ЛИТЕРАТУРА

1. Агабекян И.П., Коваленко П.И., Кудряшова Ю.А. Английский язык для психологов: Учеб. пособие для студ. высш. учеб. заведений. – М.: Изд-во Проспект, 2008 – 173 с.

2. Куликова Н.В., Мельник Л.А., Зенкевич Е.Б. Английский для студентов психологических факультетов: Учеб. Пособие. – М.: УМК Психология, 2002 – 255 с.

3. Макарова Е.А. Английский язык для психологов: Учеб. пособие. – М.: Изд-во Юрайт, 2013 – 403 с.

4. Никошкова Е.В. Английский язык для психологов: Учеб. пособие для студ. высш. учеб. заведений. – М.: Изд-во ВЛАДОС-ПРЕСС, 2003 – 160 с.

5.Семашко Л. А. Английский язык: Сборник текстов для студентов факультета психологии. – Челябинск: Изд-во ЮУрГУ, 2006. – 156 с.

6. http://study-english.info/psychology.php

7. http://en.wikipedia.org/wiki/

8. Easy English: Базовый курс: Учебник для уч-ся средней школы и студентов неязыковых вузов / Г.Е. Выборова, К.С. Махмурян, О.П. Мельгина – М.: Изд-во ПРЕСС КНИГА, 2003 – 384 с.

Наиболее известным и популярным способом решения линейных систем вида (1.1) является метод последовательного исключения неизвестных – метод Гаусса (GE). Метод существует во многих вариантах, которые алгебраически тождественны. Методы отличаются характером хранения матриц, порядком исключения, способами предупреждения больших погрешностей округления и тем, как уточняются вычисленные решения. Имеются также варианты, специально приспособленные для систем с симметричными положительно определенными матрицами, которые хранятся в примерно вдвое меньшем объеме.

Систему (1.1) приводят к треугольному виду последовательно, исключая сначала x 1 из второго, третьего, …, N -го уравнений, затем x 2 из третьего, четвертого, …, N -го уравнений преобразованной системы, и т.д. На первом этапе заменяют второе, третье, …., N -е уравнение на уравнения, получающиеся сложением этих уравнений с первым, умноженным соответственно на . Результатом этого этапа преобразований будет эквивалентная (1.1) система. На втором этапе проделывается такие же операции, как и на первом, с подсистемой полученной системы, получающейся исключением первого уравнения. Продолжая этот процесс, на (N – 1)-м этапе так называемого прямого хода метода Гаусса данную систему (1.1) приводят к треугольному виду. Очевидно, что треугольная структура системы позволяет последовательно одно за другим вычислять значения неизвестных, начиная с последнего. Этот процесс последовательного вычисления значений неизвестных называют обратным ходом метода Гаусса.

Далее приведен простой алгоритм решения СЛАУ методом Гаусса.

Алгоритм метода Гаусса

Для k = 1, 2,…, N - 1
Для i = k + 1, …, N
tik = aik / akk
bi = bitik bk
Увеличить i
Для j = k + 1, …, N
aij = aijtik akj
Увеличить j
Увеличить k
x N = bN / aNN
Для k = N - 1, …, 2, 1
Увеличить k

Инициализируем в системе матрицу (см. методические указания к системе) real_m для действительно случая и complex_m для комплексного случая. Далее инициализируем вектор (однострочную матрицу) свободных членов right_r и right_c для действительного и комплексного случая соответственно. Пример использования метод Гаусса в системе TALGAT будет иметь вид:

- действительный случай: SET "solve" GE_r real_m right_r;

- комплексный случай: SET "solve" GE complex_m right_c.

Результат выполнения программы можно с помощью команды ECHO TO_STRING solve.

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

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

Частичное упорядочивание по столбцам требует внесение в алгоритм следующих изменений: между строками 1 и 2 нужно сделать вставку (чтобы частичное упорядочивание было эффективным, перед этим целесообразно произвести масштабирование системы, например, разделить все числа каждой строки на наибольшее число строки):

Å   «Найти m ³ k такое, что ; если amk = 0, остановить работу алгоритма («однозначного решения нет»), иначе поменять местами bk и b m, akj и amj при всех j = k, …, N»

Пример использования метода исключения Гаусса с частичным упорядочиванием по столбцам в системе TALGAT:

- действительный случай: SET "solve" PGE_r real_m right_r;

- комплексный случай: SET "solve" PGE complex_m right_c.

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

1.2 LU–разложение матриц

Пусть – данная N ´ N -матрица, а и – соответственно нижняя (левая) и верхняя (правая) треугольные матрицы. Справедливо следующее утверждение. Если все главные миноры квадратной матрицы A отличны от нуля, то существуют такие нижняя L и верхняя U треугольные матрицы, что A = LU (главными минорами матрицы называются определители подматриц , где k = 1, 2,…, N – 1). Если элементы диагонали одной из матриц L или U фиксированы (ненулевые), то такое разложение единственно.

Реализация LU-разложения с фиксированием диагонали верхней треугольной матрицы называется методом Краута. Рассмотрим разложение матриц при фиксировании диагонали нижней треугольной матрицы (lij = 1 при i = j) – метод Дулитла. Далее находят lij при i > j (lij = 0 при i < juij при i £ j (uij = 0 при i > j) такие, чтобы

´

Выполнив перемножение матриц, на основе поэлементного приравнивания левых и правых частей приходим к N ´ N матрице уравнений

относительно N ´ N -матрицы неизвестных

u 11, u 12, …, u 1 N (1.3)
l 21, u 22, …, u 2 N
……………….
lN 1, lN 2, …, uNN

Легко видеть, что все отличные от 0 и 1 элементы матриц L и U могут быть однозначно вычислены с помощью всего двух формул

(где i £ j), (1.4)
(где i > j). (1.5)

При внимательном рассмотрении приведенных преобразований можно заметить, что для реализации LU-разложения по данным формулам существует большое количество различных методов, например, построчное вычисление, т.е. пока не вычислена i -ая строка матриц L и U, алгоритм не модернизирует i +1 строку.

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

Во-первых, организация вычислений по формулам (1.4) – (1.5) должна предусматривать переключение счета с одной формулы на другую. Это удобно делать, ориентируясь на матрицу неизвестных (1.3) (ее, кстати, можно интерпретировать как N 2-мерный массив для компактного хранения LU-разложения в памяти компьютера), а именно, первая строка (1.3) вычисляется по формуле (1.4) при i = 1, j = 1, 2,…, N; первый столбец (1.3) (без первого элемента) – по формуле (1.5) при j = 1, i = 2,…, N, и т.д.

Во-вторых, препятствием для осуществимости описанного процесса LU-разложения матрицы A может оказаться равенство нулю диагональных элементов матрицы U, поскольку на них выполняется деление в формуле (1.5). Отсюда следует требование, накладываемое на главные миноры. Для определенных классов матриц требования о разложении заведомо выполняются. Это относится, например, к матрицам с преобладанием диагональных элементов.

Далее приведена построчная схема LU-разложения (так называемая ikj -версия).

Алгоритм LU-разложения ( ikj -версия)

Для i = 2, …, N
Для k = 1, …, i – 1
aik = aik / akk
Для j = k + 1, …, N
aij = aijaik × akj
Увеличить j
Увеличить k
Увеличить i

Данный алгоритм позволяет пересчитать i -ю строку матрицы A в i -ю строку матриц L и U. Каждые 1, 2,…, j -1 строки участвуют в определении j -й строки матриц L и U, но сами больше не модернизируются.

Пример использования LU-разложения в системе TALGAT:

- действительный случай: SET "lu_fact" LU_FACT_r real_m;

- комплексный случай: SET "lu_fact" LU_FACT complex_m.

Как упоминалось ранее, существует много вариантов осуществления LU-разложения.




Поделиться с друзьями:


Дата добавления: 2014-12-27; Просмотров: 945; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.021 сек.