МетодиЧЕские указания для решения плохообусловленных слау методами итераций по предмету «основы алгоритмизации и программирования» на тему: «преобразование матриц: сведение матриц к матрицам с преобладающими диагональными элементами»


Скачать 151.76 Kb.
НазваниеМетодиЧЕские указания для решения плохообусловленных слау методами итераций по предмету «основы алгоритмизации и программирования» на тему: «преобразование матриц: сведение матриц к матрицам с преобладающими диагональными элементами»
Дата публикации10.03.2013
Размер151.76 Kb.
ТипМетодические указания
referatdb.ru > Информатика > Методические указания
Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет информатики и радиоэлектроники»

методиЧЕские указания

для решения плохообусловленных слау методами итераций

по предмету

«основы алгоритмизации и программирования»

на тему:

«ПРЕОБРАЗОВАНИЕ МАТРИЦ:

СВЕДЕНИЕ матриц К МАТРИЦАМ

С ПРЕОБЛАДАЮЩИМИ ДИАГОНАЛЬНЫМИ ЭЛЕМЕНТАМИ»


Автор:

студент группы 522404


_______________ Кнышев В.Н.
Руководитель:

_______________ Соловьев В.П.

МИНСК

2008


СОДЕРЖАНИЕ

3

3

4

6

9...................................................................................

10

11

13

14



Цель работы.....................................................................................

Содержание методического указания...................................................

Пути решения.....................................................................................

Алгоритм решения задачи..................................................................

Интерфейс программы.............................................................................................................................................................

Результаты проведенной работы.....................................................

Приложение 1......................................................................................

Приложение 2......................................................................................

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

^ ЦЕЛЬ РАБОТЫ

Для решения поставленной задачи написать программу с использованием основных возможностей среды программирования Delphi 7.

Использование программы в лабораторном практикуме по курсу «Основы алгоритмизации и программирования»

^ СОДЕРЖАНИЕ МЕТОДИЧЕСКОГО УКАЗАНИЯ

Программа решает следующие задачи:

      1. Задание размерности системы линейных алгебраических уравнений (далее СЛАУ) по количеству неизвестных

      2. Отыскание решений СЛАУ с неизвестными двумя методами с учетом определения корректности (плохой обусловленности):

  • прямым методом решения

        • методом Гаусса (MG)

  • итерационными методами решения

        • методом простой итерации (MI)

        • методом Зейделя (MZ)

  1. Оценка погрешностей вычисления каждым из методов

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

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

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

  5. Сравнение решений, полученных путем решения исходной СЛАУ с произвольной матрицей методом Гаусса и преобразованной СЛАУ с преобладающими элементами методом Гаусса, методом простой итерации и методом Зейделя.



^ ПУТИ РЕШЕНИЯ

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

Отыскание решения СЛАУ с неизвестными — одна из наиболее часто встречающихся задач в практике вычислительных расчетов.

Обычно СЛАУ записывается в виде



(1)

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

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

(2)

где G — матрица; — столбец свободных членов.

Одно из известных условий сходимости решения (2) и определяет структуру программы.

Приведение исходной системы к виду (2) осуществляется в два этапа:

  1. Исследование на наличие строк с преобладающими элементами в исходной системе

  2. Преобразование матрицы: отыскание недостающих строк (преобразованных) в преобразованной матрице


Обратимся к первому этапу:

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

Здесь можно столкнуться со следующими ситуациями

  1. в исходной матрице нет строк c преобладающими элементами

В этом случае сразу же переходим к отысканию недостающих строк (второй этап)

  1. в исходной матрице есть строки с преобладающими элементами

В случае если в системе найдено n отличное от единицы (больше одного) число строк с преобладающим k-тым элементом возможны также две ситуации:

    • среди n найденных строк одна является k-той в исходной системе. В данной ситуации именно эта строка будет использована в преобразованной матрице.

    • среди n найденных ни одна из строк в исходной матрице не является k-той. В данной ситуации в преобразованной матрице на месте k-той будет использована строка первая, встретившаяся в процессе обработки.

Рассмотрим пример:

Если в исходной матрице 2-ая и 5-ая строки имели 2-ой преобладающий элемент, то именно 2-ая строка будет использована в преобразованной матрице.

Если же в исходной матрице 5-ая и 7-ая строки имели 4-ый преобладающий элемент, а 4-ая строка такого элемента не имела, то в преобразованном виде будет использована первая найденная строка, т.е. 5-ая.

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

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

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

Процесс обработки исходной матрицы является построковым.

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

^ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ


исходная матрица (— копия исходной матрицы)

матрица коэффициентов

преобразованная матрица

массив, содержащий информацию о наличие преобладающего диагонального элемента

массив, содержащий информацию о необходимости преобразовывать строку

промежуточный массив, полученный домножением строки исходной матрицы на












^ ИНТЕРФЕЙС ПРОГРАММЫ




Интерфейс программы прост и понятен.

Рабочая область программы условно разделена на 2 части, которые разделены вкладками:

  • исходная система и ее решения

  • преобразованная система и ее решения

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

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

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

Рядом с преобразованной системой расположено поле, предлагающее решить преобразованную матрицу тремя методами:

  • по методу Гаусса

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

  • по методу простой итерации

(стало возможным после приведения системы к виду (2))

  • по методу Зейделя

(стало возможным после приведения системы к виду (2))
Также на рабочей области программы расположены поля, отображающие желаемую точность вычисления (задается пользователем), погрешности прямых вычислений по каждому из методов (задается пользователем), количество итераций, выполненных в результате отыскания решений (для итерационных методов, отображается после отыскания решения соответствующим методом) и количество шагов приведших к полному преобразованию исходной системы (отображается после преобразования системы).
Нажатием на кнопку «ЗАДАТЬ» пользователь задает размер исходной СЛАУ указанную в одноименном поле.

Нажатием на кнопку «ПРЕОБРАЗОВАТЬ» пользователь задает команду преобразования исходной СЛАУ к виду (2).

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

^ РЕЗУЛЬТАТЫ ПРОВЕДЕННОЙ РАБОТЫ
Написанная программа реализует в себе все поставленные задачи:

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

  • Использование нескольких методов решения

  • Отыскание погрешностей вычислений

  • Сравнение полученных всех полученных результатов (решений и погрешностей)


ПРИЛОЖЕНИЕ 1


Преобразовать систему к диагональному виду

(1)
БЛОК 1: ввод исходных данных системы



БЛОК 2: создание копии исходной матрицы данных, обнуление значений преобразованной матрицы и массива значений

БЛОК 3: вход в ЦИКЛ I:

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

БЛОК 4: вход в ЦИКЛ II:

выясняет, какой из элементов является преобладающим, перебирая и проверяя каждый на преобладание (БЛОКИ 5..10)

На выходе из ЦИКЛА I мы будем иметь массив значений, содержащий информацию о наличие преобладающего элемента:

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

БЛОК 11: вход ЦИКЛ IV:

обеспечивает присваивание элементов исходной строки элементам преобразованной при условии, что строка стоит на своем месте (БЛОК 12: если . В нашем случае все элементы третьей строки исходной матрицы станут элементами этой же третьей строки в преобразованной матрице)

В конце цикла элементу массива, содержащего информацию о необходимости преобразовывать третью строку, присваивается значение равное единицы. Это означает, что необходимости в нахождении 3-ей строки УЖЕ НЕТ — БЛОК 18

БЛОК 19: вход в ЦИКЛ V:

обеспечивает присваивание элементов исходной строки элементам преобразованной при условии, что строка содержит преобладающий элемент любой строки (БЛОК 20: если . В нашем случае все элементы второй строки исходной матрицы станут элементами первой строки в преобразованной матрице)

В конце цикла элементу массива, содержащего информацию о необходимости преобразовывать первую строку, присваивается значение равное единицы. Это означает, что необходимости в нахождении 1-ой строки УЖЕ НЕТ — БЛОК 23.

БЛОК 24: вход в ЦИКЛ IX:

основной цикл программы, выполняющий непосредственное преобразование тех строк, для которых . (БЛОК 25)

БЛОК 26: вход в ЦИКЛ X:

выполняет следующие действия:

  1. коэффициенту k присваивается значение равное 1 (БЛОК 27)

  2. устанавливаются начальные границы для значения коэффициентов домножения (БЛОК 29, ЦИКЛ XI)

  3. коэффициенту для несуществующей строки razm+1 присваивается значение k (БЛОК 30). Это делается для того, чтобы создать условие для расширения границ значений коэффициентов домножений в случае, когда не удалось найти преобразованный вид строки с текущими границами (БЛОК 45).

  4. БЛОКИ 31..42 выполняют преобразование строки и выполняют проверку на преобладание диагонального элемента (БЛОК 39). Если условие преобладания выполняется, то выполняется ЦИКЛ XV:

    • присваивание элементам преобразованной матрицы значений найденных элементов

    • меняется значение условия выхода en из ЦИКЛА X

БЛОК 43: коэффициенту nmb присваивается значение равное (-1).

БЛОК 44: вход в ЦИКЛ XVI:

здесь осуществляется поиск двух предельных значений коэффициента nmb (равных k). Для того, чтобы учесть последнюю строку и вводится несуществующая строка (см. БЛОК 30)

Значение коэффициента nmb означает возможные ситуации для изменения границ коэффициентов домножения:

БЛОК 47: nmb=1 — это значит, что все возможные преобразования (с текущими границами коэффициентов) были выполнены. Необходимо расширить границы (БЛОК 48)

БЛОК 52: nmb>1 — это значит, что некоторая строка внутри матрицы уже была домножена на все возможные коэффициенты (используя текущие границы). Необходимо увеличить значение коэффициента домножения строки, находящейся на одну позицию выше, на единицу, а значения коэффициентов всех последующих строк изменить на (-k)

БЛОК 57: nmb=-1 — это значит, что ни для одной из строк коэффициент домножения не достиг предельного значения. В этом случае необходимо увеличить на единицу коэффициент домножения последней строки (БЛОК 58).


ПРИЛОЖЕНИЕ 2

^ ТЕСТОВЫЙ ПРИМЕР
В качестве тестового примера предлагается исследовать СЛАУ
, имеющую решение .
В таблице 1 приведены значения результата выполнения программы при условии ε=0,001 для каждого из способов отыскания решения как для исходной, так и для преобразованной матрицы.
ТАБЛИЦА 1

^ ИСХОДНАЯ МАТРИЦА

MG

MI

MZ

РЕШЕНИЕ

НЕВЯЗКА

2,74

-1,18

3,17

2,18

0,09688

0,00001





1,12

0,83

-2,16

-1,15

1,77317

0,00000





0,18

1,27

0,76

3,23

1,26400

0,00000














^ ПРЕОБРАЗОВАННАЯ МАТРИЦА

MG

MI

MZ

РЕШЕНИЕ

НЕВЯЗКА

РЕШЕНИЕ

ЧИСЛО

ИТЕРАЦИЙ

РЕШЕНИЕ

ЧИСЛО

ИТЕРАЦИЙ

-4,04

-0,92

-1,77

-4,26

0,09688

0,00001

0,09650

22

0,09663

15

0,18

1,27

0,76

3,23

1,77317

0,00000

1,77278

1,77297

1,12

0,83

-2,16

-1,15

1,26400

0,00000

1,26444

1,26379



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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


  1. Синицын А. К., Навроцкий А. А. “Алгоритмы вычислительной математики” — Мн., БГУИР, 2007. — 80с.:ил.




кнышев в.н. «преобразование матриц: сведение матриц к матрицам с преобладающими диагональными элементами»

стр. из


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

«Аналитическая геометрия и высшая алгебра»
...
Программа вступительного экзамена в магистратуру специальности 6М051800...
Умножение матриц. Транспонирование матрицы. Определители квадратных матриц. Свойства определителей. Теорема Лапласа. Обратная матрица....
Вопросы к экзамену по курсу «Алгебра и геометрия»
Спектр матриц. Матрицы с простым спектром. Приведение матриц к диагональному виду
Методические указания для самостоятельной работы студентов под руководством...
Цель: освоение основ алгоритмизации задач, изучение порядка действий и получение теоретической основы программирования линейных,...
А. Д. Казмерчук в данной работе вводится класс разреженных матриц...
В данной работе вводится класс разреженных матриц специального вида – фракталоподобных матриц (Fractal-like matrices). Множество...
Программа вступительного экзамена по дисциплине «Основы алгоритмизации и программирования»
«Основы алгоритмизации и программирования» для абитуриентов, поступающих на сокращенную заочную форму обучения по специальности
Вопросы к экзамену по дисциплине «Основы алгоритмизации и программирования»
Голицина О. Л., Попов И. И. Основы алгоритмизации и программирования. – М: форум: инфра-м, 2004. – 432с. – (серия “Профессиональное...
Критерии оценки знаний абитуриентов по дисциплине «Основы алгоритмизации и программирования»
Программы вступительного экзамена по дисциплине «Основы алгоритмизации и программирования» для абитуриентов, поступающих на сокращенную...
Методические указания по курсовому проектированию по дисциплине «основы...
Методические рекомендации по выполнению курсового проекта разработаны преподавателем спец дисциплин Н. А. Салий
Программа по дисциплине «основы алгоритмизации и программирования»
Целью изучения дисциплины является подготовка специалиста, владеющего фундаментальными знаниями и практическими навыками в области...

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


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза