Завдання

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Де

Алгоритм

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

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

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

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

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

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

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

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

Вигляд РЛ-числа Алгоритм переведення числа з десяткової системи числення в РЛ ВХІД: Х¹⁰, max.

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

I. А =Х, k = max.

2.R= A-2^k.

3.Якщо R = 0, то Х^рл

4.Якщо R<0, k

5.k

6.А

7.Х^рл

8.Перехід 2.

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

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

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

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

l. S<0.

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

2.1. S^Nxi

3. X¹⁰

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= {А, Х}.

5.Реалізувати алгоритми сортування АS та приведення подібних АР для масиву Y.

6.Результат

Алгоритм множення ВХІД: A = sign A Q_A {a_i}; В = sign В Q_B{b_i}.

РЕЗУЛЬТАТ: X= sign X Q_x{X_i}.

1.Визначення знаку добутку sign X=sign A*sign В.

2.Формування масиву часткових добутків X={х_i}.

2.1. Для і = 1 до QA виконувати:

2.1.1.Для j = 1 до QB виконувати:

2.1.2.Х_k = аi + b_j.

3.Для масиву X застосувати алгоритми AS та АР.

4.Результат > X.

Алгоритм ділення ВХІД: А = sign A Q_A {а_i}; В = sign В Q_B{b_i}.

РЕЗУЛЬТАТ: R = A/ В = sign R Q_R {r_i}.

1. Якщо B = 0, то КІНЕЦЬ ОБЧИСЛЕНЬ, інакше 2.

2. Визначити знак результату.

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

3.1. ri= СЗО (А або O_i=O_i-1) — СЗО (В).

3.2. Обчислити В*{ri}.

3.3. Визначити O_i=A (O_i-1) — В*{ri}.

3.4. Якщо O_i < 0, то r_i = r_i— 1 перейти до 3.2, інакше 3.1.

4. Результат R = А/В = sign R Q_R {r_i}.

Алгоритм знаходження оберненої матриці за методом Крамера

1. Знайти визначник матриці A.

2. Якщо det (A)?0, то перехід 3.

Якщо det (A)=0, то перехід 6.

3. Обчислити союзну матрицю А*.

4. Знайти транспоновану матрицю А^т .

5. Знайти обернену матрицю А^-1 = А^т.

6. Зворотньої матриці не існує.

Розробка програми

Програму було розроблено засобами середи розробки MS Visual Studio 2010 на мові програмування С#. На першому етапі розробки було створено клас для роботи з рл-числами. Цей класс включає в себе всі головні операції роботи рл-чисел.

Код класу RL

class RL

{

private List mantisa;

private int Q;

private bool Negative;

private int MZO, SZO;

private void ReverseSign ();

public override string ToString ();

public RL ();

public RL (string value);

static public RL Parse (string value);

public static double fromRL (RL num);

private void Sort ();

private void Combine (RL rl);

private void Similar ();

private void DelIdent (RL rl);

public RL Abs ();

public RL Clone ();

static public RL operator -(RL RL1, RL RL2);

public static bool operator >(RL rl1, RL rl2);

static public RL operator —(RL rl1);

static public RL operator ++(RL rl1);

public static bool operator <(RL rl1, RL rl2);

public static bool operator ≠(RL rl1, RL rl2);

static public RL operator *(RL rl1, RL rl2);

public static bool operator ==(RL rl1, RL rl2);

private int IsBigger (RL rl);

private int CompareTo (object obj);

static public RL operator +(RL RL1, RL RL2);

public static RL operator /(RL RL1, RL RL2);

public static RL FromDec (int Num);

public static RL ToRL (string Num);

private RL Pow (int i);

}

В класі РЛ було запрограмовано такі операції як +,-*,/ для подальшого застосування їх в розрахунку алгоритма знаходження зворотньої матриці методом Гауса.

Для ділення було застосовано алгоритм частки углом.

Код для «/»

public static RL operator /(RL RL1, RL RL2)

{

RL rl1 = RL1. Abs ();

RL rl2 = RL2. Abs ();

if (rl1.Q == 0) return new RL («0.0»);

RL resultRL = new RL ();

resultRL.Negative = true;

if (RL1.Negative && RL2. Negative) resultRL. Negative = false;

if (!RL1.Negative && !RL2.Negative) resultRL. Negative = false;

if (rl1 == rl2)

{

resultRL.mantisa.Add (0);

resultRL.Q = 1;

return resultRL;

}

List result = new List ();

RL first = new RL («0.0»);

RL @null = new RL («0.0»);

first.Negative = false;

int count = 0;

RL current = first * rl2;

while (rl1.mantisa.Count ≠ 0 && count < 10)

{

if (rl1 > rl2)

{

while (rl1 > current)

{

if (first.mantisa.Count == 0) first.mantisa.Add (0);

else

first.mantisa[0] = first. mantisa[0] + 1;

current = first * rl2;

}

if (rl1 ≠ first * rl2)

{

first.mantisa[0] = first. mantisa[0] - 1;

}

rl1 -= first * rl2;

resultRL.mantisa.Add (first.mantisa[0]);

first = new RL («0.0»);

current = first * rl2;

}

else

{

current = rl2;

while (rl1 < current)

{

if (first.mantisa.Count == 0) first.mantisa.Add (-1);

else

first.mantisa[0] = first. mantisa[0] - 1;

current = first * rl2;

}

if (rl1.mantisa.Count ≠ 0 && first.mantisa.Count ≠ 0)

{

rl1 = (rl1 — first * rl2).Abs ();

resultRL.mantisa.Add (first.mantisa[0]);

first = @null;

count++;

}

else break;

}

}

resultRL.Q = resultRL.mantisa.Count ();

resultRL.MZO = resultRL.mantisa.Max ();

resultRL.SZO = resultRL.mantisa.Min ();

return resultRL;

}

Для множення було застосовано алгоритм множення за допомогою матриць

Код для «*»

static public RL operator *(RL rl1, RL rl2)

{

if (rl1.mantisa.Count == 0 || rl2.mantisa.Count == 0) return new RL («0.0»);

RL result = new RL ();

result.Negative = true;

if (rl1.Negative && rl2. Negative) result. Negative = false;

if (!rl1.Negative && !rl2.Negative) result. Negative = false;

foreach (var item1 in rl1. mantisa)

{

foreach (var item2 in rl2. mantisa)

{

result.mantisa.Add (item1 + item2);

}

}

result.Sort ();

result.Similar ();

result.Q = result.mantisa.Count;

result.SZO = result.mantisa.Max ();

result.MZO = result.mantisa.Min ();

return result;

}

програмний логарифмічний кодування гаус

Реалізація алгоритму Гауса

Для рл-чисел та для звичайних числе алгоритм Гауса є однаковим. В даному тексті приведено код для рл-чисел, який є таким самим для звичайних

public Matrix rlgaussa (Matrix AA, int N)

{

RL[,] mas=new RL[N, N];

RL temp;

for (int i=0;i

for (int j = 0; j < N; j++)

{

mas[i, j] = RL. ToRL (AA[i, j]. ToString ());

}

RL[,] E = new RL[N, N];

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

{

E[i, j] = RL. FromDec (0);

if (i == j)

E[i, j] = RL. FromDec (1);

}

for (int k = 0; k < N; k++)

{

temp = mas[k, k];

for (int j = 0; j < N; j++)

{

mas[k, j] =mas[k, j]/ temp;

E[k, j] =E[k, j]/ temp;

}

for (int i = k + 1; i < N; i++)

{

temp = mas[i, k];

for (int j = 0; j < N; j++)

{

mas[i, j] =mas[i, j]- mas[k, j] * temp;

E[i, j] = E[i, j]-E[k, j] * temp;

}

}

}

for (int k = N — 1; k > 0; k—)

{

for (int i = k — 1; i >= 0; i—)

{

temp = mas[i, k];

for (int j = 0; j < N; j++)

{

mas[i, j]=mas[i, j]- mas[k, j] * temp;

E[i, j]=E[i, j]- E[k, j] * temp;

}

}

}

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

mas[i, j] = E[i, j];

Matrix BB=new Matrix (N, N);

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

BB[i, j] = Math. Round (RL.fromRL (mas[i, j]), 15);

return BB;

}

Результати роботи програми

Висновок

З результатів роботи програми можно зробити висновок, що за допомогою рл-чисел можна значно покращити точність розрахунків. Ця точність досягається шляхом зберігання рл-числа за допомогою масива. В той самий час звичайні числа не дозволяют досягти такої точності.

Список використованної літератури

1. Гамаюн В. П. Моделювання багаторозрядних систем: Навч. посібник — К.:Видавництво національного авіаційного університету, 2007. — 112 с.

2. Денисюк В. П. Репета В.І., Вища математика, 1 ч. — К.:Видавництво національного авіаційного університету, 2006. — 15−20 с.

3. Дональд Кнут. Мистецтво програмування. Алгоритми і структури даних. Т.2. — MIT Press, 1997. 43−67 ст.

4. Мудров А. Я. Чисельні методи для ЕОМ на мові Pascal, Fortran і Basic. — К.:Видавництво КМУЦА, 1975. — 30−45 с.