Тема 6 Андриевский. Изучение метода Жордана с полным выбором ведущего элемента

• Название: Изучение метода Жордана с полным выбором ведущего элемента
• Дата: 28.03.2023
• Размер: 2.07 Mb.
• Имя файла: Тема 6 Андриевский.doc
• Тип: Курсовой проект; #1021151

Восточно-Сибирский государственный университет технологии и управления.

Кафедра ЭСППиСХ


Допущен к защите

Руководитель проекта:

Кривошеин М.Ю.

“___”___________2020 г.


КУРСОВОЙ ПРОЕКТ

по курсу: Основы алгоритмизации энергетических задач.

на тему: Изучение метода Жордана с полным выбором ведущего элемента.

Студент 2 курса,

гр.ЗБ-639-2: Андриевский Я.А.

Улан-Удэ

2020

Восточно-Сибирский государственный университет технологий и управления

Кафедра ЭСПП и СХ
“Утверждаю”

Зав. кафедрой

____________________

“___”___________2020 г.

Задание

по курсовому проектированию

Студенту 2 курса ЗБ-639-2 группы Электротехнического факультета

Фамилия Андриевский Имя Ян Отчество Андреевич

Срок выполнения проекта__________________ 2020 г.

Защита проекта назначена на__________________ 2021 г.

Время выдачи задания__________________ 2020 г.

1. 
   Тема проекта
   

Изучение метода Жордана с полным выбором ведущего элемента.

2. 
   Задание и содержание расчетно-пояснительной записки
   

Введение

Изучение метода Жордана с полным выбором ведущего элемента. Вместо приведения матрицы А к треугольному виду можно попытаться сделать ее диагональной. На k-м шаге, имея ненулевой главный элемент, можно исключить все элементы (кроме диагонального) k-го столбца матрицы А. Вычисления аналогичны вычислениям по методу Гаусса; также допускается перестановка строк и столбцов и на n-1 шаге решается система линейных уравнений с диагональной матрицей.

Цель темы состоит в оценке этого метода. Взяв за основу алгоритм Дулиттла А1.4 [11] (метод LU-разложения), необходимо выполнить следующие задания.

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

2. Составить программу решения Ах=b с использованием этого алгоритма.

3. Завершить тему выполнением всех заданий темы 1.


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

Сборник алгоритмов решения систем линейных уравнений. Методические указания к практическим занятиям, курсовому проектированию и СРС.ВСГТУ, Улан-Удэ 2012 год
Руководитель проекта: Кривошеин М.Ю.

Задание принял к исполнению «___»______________2020г. ____________

(дата и подпись студента)



РАСЧЕТНО - ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Основной раздел

1. Теоретические аспекты численных методов

В данной курсовой работе рассматривается алгоритм решения системы линейных уравнений методом Жордана с полным выбором ведущего элемента.

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

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

Постановка задачи и описание алгоритма:

Задача состоит в решении системы уравнений_{ }, где A – матрица порядка n, _{ } – вектор, состоящий из n компонент:

A = _{ }, b = _{ }

Мы будем использовать расширенную матрицу A^* , в которой вектор _{ } является n + 1 столбцом:

A^* = _{ }

Наглядно метод Жордана можно представить в виде умножения матрицы A^* на матрицы L_k (k – текущая итерация алгоритма) справа n раз:

L_k = _{ } , где l_ik= _{ }, 1 _{ }

(в скобках указывается количество изменений элемента)

L_n(L_n-1 (L_n-2 … (L_{1  } = _{ } .

Простым преобразованием _{ }= _{ }, _{ }= _{ }, _{ }получим:



Искомые решения: _{ }

Пример: найдем решения системы _{ } .

Матрица A = _{ } , b = _{ } . Расширенная матрица _{ }= _{ } .

Вычислим L₁ : l₂₁ = _{ }, L₁ = _{ }; L_{1  } =

_{ } . Теперь найдем L₂ : l₁₂ = _{  } = _{ } , L₂ = _{ } ;

L₂(L_{1 } = _{ } .

Приведем часть A матрицы _{ } к единичному виду: _{ }

и получим _{ }

Проверка: _{ } – верно.

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

Заметим, что при перестановке столбцов изменяется порядок переменных в уравнениях. Чтобы вывести корректный ответ, необходимо завести строку длины n и заполнить ее числами от 1 до n последовательно. При перестановке столбцов меняются местами элементы этой строки, с индексами, равными номерам столбцов соответственно.

Теперь рассмотрим реализацию алгоритма метода Жордана на ЭВМ. Она будет отличаться от наглядной, так как нерационально хранить и вычислять матрицы L_k . Мы также используем расширенную матрицу A^* , а все вычисления сводятся к двум операциям:

1. Умножение строки на множитель

2. Сложение одной строки с алгебраическим дополнением к другой (вычитание строк)

Каждая итерация k состоит из трех частей:

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

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

3. Из каждой строки, кроме k-ой, поэлементно вычитаем элементы ведущей строки, умноженные на элемент, лежащий на пересечении ведущего столбца и текущей строки.

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

Допустим, процесс прервался на s-ой итерации. Первые s строк, начиная с единицы, содержат единицу в k-ом столбце и значение k-ой переменной в столбце n + 1. Если есть строки с номерами > s, то они должны быть нулевыми, иначе система уравнений неразрешима. Это необходимо проверять. Переменные с индексами i, _{ }, называются базисными, переменные с индексами i, _{ } (если s = n, то таких переменных нет), называются небазисными и выражаются через другие, указывать в ответе их не будем.

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

2. Программная реализация

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

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

Выделим для выбора ведущего элемента и исключения столбца отдельные подпрограммы (процедуру и функцию).

Реализация на псевдокоде:

Необходимые переменные: n – количество строк, j – номер ведущей строки (столбца), A[0… n, 1 … n + 1] – расширенная матрица коэффициентов c нулевым столбцом, отвечающим за порядок переменных, i, k – итераторы, s – количество успешных итераций

function LeadElementSelection – выбор ведущего элемента

Функция принимает на вход j, n, A и определяет переменные leadingString – номер новой ведущей строки, leadingColumn – номер нового ведущего столбца, max – модуль максимального значения, выбирает ведущий элемент, изменяя матрицу А, и возвращает “true” или “false” в зависимости от того, удалось ли сделать выбор

Начало

max присвоить значение модуля A[j, j]

leadingString присвоить значение j

leadingColumn присвоить значение j

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

Для строк i от j до n:

Для столбцов k от j до n:

Если A[i, k] не равно 0 и A[i, k] больше максимума, то:

max присвоить значение модуля A[i, k]

leadingString присвоить значение i

leadingColumn присвоить значение k

Конец цикла

Конец цикла

(изменение порядка строк и столбцов, если необходимо)

Если ведущий элемент не A[j, j], то:

Если leadingString не равно j, то поменять местами строку j с leadingString поэлементно

Если leadingColumn не равен j, то поменять местами столбец j с leadingColumn местами поэлементно

Если max равен нулю, то вернуть значение “false”, иначе вернуть “true”

Конец функции

procedure ColumnElimination – исключение не ведущих элементов столбца

Процедура принимает на вход j, n, A и исключает все элементы j-того столбца кроме ведущего (A[j, j]), изменяя матрицу А.

Начало

(получаем направляющую строку с ведущим элементом, равным единице)

Для столбцов k от n + 1 до j:

A[j, k] присвоить значение _{ }

Конец цикла

(исключаем не ведущие элементы ведущего столбца)

Для строк i от 1 до n:

Если номер строки i равен j, то перейти к следующей итерации

Иначе для столбцов k от n + 1 до j:

A[i, k] присвоить значение (A[i, k] - A[j, k]*A[i, j]);

Конец цикла

Конец цикла

Конец процедуры

program JordansMethod – основная часть программы:

Начало

Присвоить числу успешных итераций s значение 0

Считать n (размер матрицы коэффициентов, число уравнений в системе)

Считать расширенную матрицу системы уравнений в A, заполнить нулевую строку числами от 0 до n последовательно

(применяем метод Жордана)

Для j от 1 до n:

Если функция LeadElementSelection(j, n, A) вернула “false”, то завершить цикл

Иначе:

Увеличить количество успешных итераций s на единицу

Вызвать процедуру ColumnElimination(j, n, A)

Конец цикла

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

Если число успешных итераций s не равно числу строк n, то:

Для строк i от s + 1 до n:

Если A[i, n + 1] равно 0, то:

(показываем, что система неразрешима)

s присвоить значение 0 (показываем, что система неразрешима)

Выходим из цикла

Конец цикла

Если s равно 0, то выводим: “Unsolvable system”

Иначе для i от 1 до s:

Вывести: “x”, A[0, i], “ = “, A[i, n + 1]

Перейти на новую строку

Конец цикла

Конец программы

Пример 1: решим систему линейных уравнений _{ } , используя представленную выше программную реализацию

Вызывается program JordansMethod.

1. Считываем n, n = 2. Считываем и заполняем матрицу А, получаем

_{ }= _{ }, где _{ } - неиспользуемая ячейка памяти. Не забываем, что индекс первой строки в матрице А равен 0.

2. Начинаем выполнение алгоритма с первого входа в функцию

LeadElementSelection с параметрами j = 1, n = 2, _{ }= _{ } :

Изначально max = 1, leadingString = 1, leadingColumn = 1.

После выбора максимального элемента получаем:

max = 2, leadingString = 2, leadingColumn = 1.

Необходимо поменять местами строки 1 и 2: _{ }= _{ }.

Функция возвращает “true”, так как выбор прошел успешно (A[1, 2] не

равно нулю).

3. Число успешных итераций s равно 1. Вызываем процедуру

ColumnElimination с параметрами j = 1, n = 2, _{ }= _{ }:

Получаем ведущую строку с ведущим элементом, равным единице –

_{ }= _{ } и вычитаем ее, умноженную на A[2, 1] = _{ } , из второй строки, чтобы A[2, 1] стало

равным 0: _{ }= _{ }.

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

не ведущие элементы из второго столбца. Вызываем LeadElementSelection с параметрами j = 2, n = 2, _{  } :

Изначально max = _{ }, leadingString = 2, leadingColumn = 2.

После выбора максимального элемента получаем:

max = _{ }, leadingString = 2, leadingColumn = 2. Так как leadingString = = leadingColumn = j, то строки и столбцы переставлять не нужно.

Выбор ведущего элемента прошел успешно, возвращаем “true”.

5. Число успешных итераций s равно 2. Вызываем процедуру

ColumnElimination с параметрами j = 2, n = 2, _{   } :

Получаем ведущую строку с ведущим элементом, равным единице –

_{ }= _{ } и вычитаем ее, умноженную на A[1, 2] = _{ } , из первой строки, чтобы A[1, 2] стало равным 0: _{ }= _{ }.

6. Цикл завершился, делаем проверку на разрешимость: s равно n,

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

x1 = -4

x2 = 1

Программа завершена



Пример 2 : Попробуем найти решения системы _{ } .

n = 2, _{ }= _{ }

После первой итерации получим: s =1, _{ }= _{ }.

Переходим ко второй итерации. Вызываем функцию LeadElementSelection с параметрами j = 2, n = 2, _{ } max = _{ }, leadingString = 2, leadingColumn = 2. После поиска главного элемента max все еще равно 0, а значит выбор главного элемента прошел неудачно. Функция возвращает “false”

Проверяем систему на разрешимость, так как s не равно n, проверяя строки от s + 1 до n на равенство последнего элемента в строке нулю. В данном случае во второй строке последний элемент не равен нулю, то есть: _{ } – неверное равенство, следовательно система неразрешима. Выводим ответ “Unsolvable system”. Программа завершена.

Подробнее о программной реализации.

Основные параметры программы регулируются константами:

MaxMatrixSize – отвечает за выделение памяти на двумерный массив (расширенную матрицу коэффициентов). Под хранение матрицы отводится (MaxMatrixSize + 1) * (MaxMatrixSize + 1) * 6 байт (хранятся значения типа Real). По умолчанию равен 50.

NumberLength – количество символов в числе во время вывода. Применяется для удобного отображения значений. По умолчанию равно 10.

Accuracy – видимая точность вычислений, количество цифр после запятой в числе во время вывода. Число округляется , чтобы соответствовать точности.

По умолчанию равна 4.

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

Ввод

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

Затем вводится расширенная матрица коэффициентов, состоящая из n строк по n + 1 элементов, где n + 1 столбец – столбец правых частей уравнения.

Для выхода из программы нужно нажать клавишу “Enter”.

Так выглядит результат работы программы:



Или так:



Исходный код программы прилагается в файле JordansMethod.pas. Также прилагаются JordansMethod.exe – работающая версия программы и ReadMe.txt – руководство по использованию программы.



3. Вычислительные эксперименты

Временная сложность алгоритма

Оценим сложности подпрограмм: LeadElementSelection = _{ }. ColumnElimination = _{ }.

Теперь оценим сложность главной функции:

program JordansMethod = _{ } Это грубая оценка, потому что количество итераций в циклах зависит не только от n, но и от j, которое принимает значения от 1 до n.

Чтобы более точно определить сложность, посчитаем количество операций. Мы рассматриваем случай, когда система из n уравнений имеет n решений, то есть алгоритм не обрывается. Тогда выполняется:   Это совпадает с полученной оценкой временной сложности алгоритма.

Объемная сложность алгоритма

В главной функции используются следующие переменные и структуры данных: Matrix (массив значений типа Real размера (n+1)*(n+1) ) и n, i, j, s типа Integer. Это занимает ((n+1)*(n+1)*6 + 4*2) байт. Теперь найдем наибольший объем памяти, занимаемый локальными переменными вызываемых процедур и функций, он равен (2*6 + 4 * 2) байт (в функции LeadElementSelection). Тогда максимальный объем занимаемой памяти: (n+1)*(n+1)*6 + 4*2 + 2*6 + 4 * 2 = _{ }Зависимость объема занимаемой памяти от размера матрицы: _{ }

Оценка сложности выполнения программы

Предложенная функция GetTime считает время с точностью до сотых секунды – такой точности не достаточно, поэтому здесь используется функция QueryPerformanceCounter из модуля Windows, чтобы замерять время выполнения в микросекундах. Сначала определяем тактовую частоту процессора с помощью QueryPerformanceFrequency, затем с помощью двух вызовов функции QueryPerformanceCounter до и после блока с алгоритмом находим количество тактов процессора, делим их разность на количество тактов в микросекунду – это и есть искомое время работы алгоритма. При этом программа строит случайную матрицу заданного порядка и выводит время в микросекундах. (В качестве генератора случайных чисел используется функция Random, так как предлагаемая в методическом пособии функция Urand не работает).

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









И характеристический профиль:



Как мы видим, результаты эксперимента совпали с вычисленной ранее временной сложностью алгоритма (_{ }

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

Хорошо обусловленные матрицы можно создать с помощью заполнения матрицы коэффициентов случайными числами. В качестве решения системы уравнений мы предполагаем 1, 1, …, 1 – все переменные равны 1. Исходя из этого, мы строим правые части системы _{ }. Относительную погрешность вычислений рассматриваем как максимальную разность между полученным значением и единицей по отношению к полученному значению. Для этого изменим код программы, чтобы создавать матрицу таким образом и получать на выходе погрешность вычислений.

Полученные значения имеют вид:





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



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



Как мы видим, функция зависимости относительной погрешности от порядка матрицы близка к квадратичной функции: _{ }где n –порядок матрицы.

Теперь найдем зависимость относительной погрешности от числа обусловленности матрицы. Для этого проведем 30 измерений погрешности при зафиксированном порядке матрицы (пусть n равно 50).

Полученные значения имеют вид:



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



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

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

Оценка точности вычисления программы для плохо обусловленных матриц

В качестве плохо обусловленной матрицы будем использовать матрицу Гильберта ( A[i, j] = 1/(i + j - 1) ). Перепишем программу, чтобы она создавала матрицы Гильберта порядка n и выводила относительную погрешность для системы уравнений с такой матрицей. Получаем:



В виде характеристического профиля:



Явной зависимости не наблюдается, что характерно для плохо обусловленных матриц. Стоит отметить, что относительная погрешность вычислений с плохо обусловленной матрицей больше чем с хорошо обусловленной матрицей на величину от 13 до 24(!) порядков, что говорит об огромной погрешности в вычислениях с плохо обусловленной матрицей.

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



Как мы видим, порядок ведущего элемента уменьшается поитерационно. Это сильно влияет на точность измерений, так как в алгоритме используется деление элементов строки на ведущий элемент. С увеличением порядка матрицы степень минимального ведущего элемента уменьшается. Таким образом, в матрице порядка 50 степень минимально ведущего элемента равна -19. Отобразим это на характеристическом профиле:



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



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

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

Подробнее о программной реализации

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

Список используемой литературы
1. Электрические системы. Математические задачи электроэнергетики/ Под ред. В.А. Веникова. Т.1 - М.: Высшая школа, 2011. - 334с.

2. Курбацкий В.Г., Томин Н.В. Математические задачи электроэнергетики Ч.1: учеб. пособие для вузов/ Курбацкий В.Г. и др.- ГОУ ВПО «БрГУ», 2009.-142с.

3.Давыдов В.В., Борисов Г.О. Программирование матричных вычислений в электротехнических задачах. Сборник алгоритмов

решения систем линейных уравнений. Улан-Удэ, 1997.

4.Райс Дж. Матричные вычисления и математическое обеспечение. - М.: Мир, 1984. - 246 с