Размещено на http://www.allbest.ru/

Завдання

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

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

6.Результат <Y.

Алгоритм множення

ВХІД: 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<int> 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<int> result = new List<int>();

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<N;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 с.

Размещено на Allbest.ru