Розробка програмних модулів базових операцій обробки на підставі розрядно-логарифмічного кодування. Дослідження алгоритму розв'язку системи лінійних алгебраїчних рівнянь. Реалізація алгоритму Гауса. Покращення точності розрахунків за допомогою рл-чисел.
Краткое сожержание материала:

Размещено на

Завдання

1. Розробка програмних модулів базових операцій обробки на підставі розрядно-логарифмічного кодування

2. Реалізація варіанту курсової роботи як обчислення зворотніх матриць

3. Порівняльний аналіз виконується з варіантом виконання традиційними засобами ЕОМ за методами Гауса та Крамера

Варіант 9

Обчислення зворотної матриці методом Гауса.

Метод перевірки: діагональна матриця

Теоретичні відомості

Метод Гауса -- алгоритм розв'язку системи лінійних алгебраїчних рівнянь.

Початок алгоритму.

Прямий хід: Шляхом елементарних перетворень рядків (додавань до рядка іншого рядка, помноженого на число, і перестановок рядків) матриця приводиться доверхньотрикутного вигляду(ступінчатого вигляду).

З цього моменту починається зворотний хід.

З останнього ненульового рівняння виражаємо кожну з базисних змінних через небазисні і підставляємо в попередні рівняння. Повторюючи цю процедуру для всіх базисних змінних, отримуємо фундаментальний розв'язок.

Нехай вихідна система виглядає наступним чином

Матриця А називається основний матрицею системи,b - стовпцем вільних членів.

Тоді відповідно до властивості елементарних перетворень над рядками основну матрицю цієї системи можна привести до східчастого увазі (ці ж перетворення потрібно застосовувати до колонки вільних членів):

При цьому будемо вважати, що базисний мінор (ненульовий мінор максимального порядку) основної матриці знаходиться у верхньому лівому куті, тобто в нього входять лише коефіцієнти при змінних [3].

Тоді змінні називаються головними змінними. Всі інші називаються вільними.

Якщо хоча б одне число, де, то розглянута система несумісна, тобто у неї немає жодного рішення.

Нехай для будь-яких.

Перенесемо вільні змінні за знаки рівностей і поділимо кожне з рівнянь системи на свій коефіцієнт при самому лівому (, де - номер рядка):



Де

Алгоритм

Алгоритм розв'язання СЛАР методом Гауса підрозділяється на два етапи.

· На першому етапі здійснюється так званий прямий хід, коли шляхом елементарних перетворень над рядками систему призводять до ступінчастою або трикутній формі, або встановлюють, що система несумісна. А саме, серед елементів першого стовпця матриці вибирають ненульовий, переміщують його на крайнє верхнє положення перестановкою рядків і віднімають вийшла після перестановки перший рядок з інших рядків, Домножимо її на величину, рівну відношенню першого елемента кожної з цих рядків до першого елемента першого рядка, обнуляючи тим самим стовпець під ним. Після того, як зазначені перетворення були здійснені, перший рядок і перший стовпець подумки викреслюють і продовжують поки не залишиться матриця нульового розміру. Якщо на якийсь із ітерацій серед елементів першого стовпця не знайшов ненульовий, то переходять до наступного колонку і проробляють аналогічну операцію.

· На другому етапі здійснюється так званий зворотний хід, суть якого полягає в тому, щоб висловити все отримані базисні змінні через небазисні і побудувати фундаментальну систему рішень, або, якщо всі змінні є базисними, то виразити в чисельному вигляді єдине рішення системи лінійних рівнянь. Ця процедура починається з останнього рівняння, з якого висловлюють відповідну базисну змінну (а вона там всього одна) і підставляють в попередні рівняння, і так далі, піднімаючись по «сходинках» наверх. Кожному рядку відповідає рівно одна базисна змінна, тому на кожному кроці, крім останнього (самого верхнього), ситуація в точності повторює випадок останнього рядка.

Метод Гаусса вимагає O(n³) арифметичних операцій.

Розрядно-логарифмічного аріфметика

Розрядно-логаріфмічним кодуванням даних називають зображення двійкового операнда у вигляді набору двійкових кодів ненульових разрядів {Nx_i} того самого операнда, кожний з котрих визначається як результат обчислення логаріфму від ваги цього розряду:

де x_i- ненульовий розряд,

p- основна система числення.

Вигляд РЛ-числа

Алгоритм переведення числа з десяткової системи числення в РЛ

ВХІД: Х¹⁰, max.

РЕЗУЛЬТАТ: { Х^рл }.

I. А =Х, k = max.

2.R= A-2^k.

3.Якщо R = 0, то Х^рл <k, перехід 9, інакше 4.

4.Якщо R<0, k<k-1, перехід 2, інакше 5.

5.k<k-1

6.А<R.

7.Х^рл<k

8.Перехід 2.

9.РЕЗУЛЬТАТ: { Х^рл }.

Алгоритм переведення РЛ-числа в десяткову систему числення.

ВХІД: X_РЛ = sign X, q,{Nx₁, Nx₂, Nx₃, Nx₄ ....Nx_q}.

РЕЗУЛЬТАТ: X¹⁰.

l. S<0.

2.Для i = 1 до q виконувати:

2.1. S<S+2^Nxi

3. X¹⁰<S.

4.РЕЗУЛЬТАТ: X¹⁰.

Алгоритм порівняння

ВХІД: А = sign A Q_A {а_i}; В = sign В Q_B{b_i}.

РЕЗУЛЬТАТ: Р₁ (А = В), Р₂ (А ?В).

1.Якщо sign А = sign В, то перейти до 2, інакше 5.

2.Якщо Q_A = Q_B то перейти до 3, інакше 5

3.Для i = 1 до Q_A виконувати:

3.1. Якщо N^A_i = N^B_i то цикл, інакше 5.

4.Результат: Р₁ (А = В).

5.Результат : Р₂ (А ? В).

Алгоритм приведення подібних(AP) та сортування(AS)

AS:

ВХІД: А = sign A Q_A {а_i}; В = sign В Q_B {b_i}.

РЕЗУЛЬТАТ: {a_l...a_k...b_f...b_i}; а₁? ...а_k? ..b_f ? b_i.

1.Об'єднання структур РЛ кодів А та кодів В у масив

2.Обчислення загального індексу Q = Q_A + Q_B

3.Для і = 1 до Q - 1 виконувати:

3.1. ЯКЩО Х_і ?Х_i+1, то перепис кодів (С = X_j, X_j = X_{1 +і} X₁₊₁=C)

РЕЗУЛЬТАТ: X = {х₁..х_k..х_f..х_i}; а₁? ...а_k? ..b_f ? b_i.

AP:

ВХІД: А = sign A Q_A {а_i}; В = sign В Q_B{b_i}.

РЕЗУЛЬТАТ: X={х₁..х_k..х_f..х_i}; x₁?..x_k?..x_f ?…x_i.

1.Об'єднання структур РЛ кодів А та кодів В у масив

2.Обчислення загального індексу Q = Q_A + Q_B

3.Для i= 1 до Q - 1 виконувати:

3.1. Якщо х_i ? x_i+1, то x_i =х_i + 1; виключення елемента х_{i + 1} шляхом виконання зсуву масиву X на один елемент; Q=Q-1 перехід на 3.

РЕЗУЛЬТАТ: X= { х₁..х_k..х_f..х_i}; x₁?..x_k?..x_f ?…x_i.

Алгоритм додавання

ВХІД: А = sign A Q_A {аi}; В = sign В Q_B{b_i}.

РЕЗУЛЬТАТ: S = sign S Qs{s_i}

1.Перевірка на рівність нулеві операндів.

2.Об'єднання структур PJI кодів А та кодів В у масив X.

3.Обчислення загального індексу Q=Q_A + Q_B

4.Викликати Алгоритм AS для обробки масиву X.

5.Викликати Алгоритм АР для обробки масиву.

6.Встановити знак результату sign S.

РЕЗУЛЬТАТ: s= sign S Q_s{s_i}.

Алгоритм віднімання

ВХІД: А = sign А Q_A{a_i}, В = sign В Q_B{b_i}.

РЕЗУЛЬТАТ: V= sign VQ_v{V_i}.

1.Для i= 1 до min (Q_A, Q_B) виконувати:

1.1. Якщо а_i = b_i то а_i = 0, b_i, = 0, Q_A = Q_A -1, Q_B = Q_B - 1

2.Обчислити СЗОЕ А -- МЗО В, сформувати масив массив X.

3.Для i=1 до min (Q_x, Q_B) виконувати:

3.1. Якщо х_i = b_і, то х_i = 0, b_i = 0, Q_x = Q_x -1, Q_B = Q_B - 1

4.Сформувати масив Y= {А, Х}.