Решение слау методом гаусса java

Метод Гаусса в Java

Я пытался реализовать Matrix.class, чтобы узнать некоторые Java. Прямо сейчас у меня есть некоторые трудности с методом, который должен возвращать матрицу после исключения Гаусса, который будет использоваться для поиска обратной матрицы позже.
Вот что я придумал до сих пор:

В то время как функция getArray() возвращает double[][] матрицы, getHeight() и getWidth() возвращают inv.length и inv[0].длина респектабельно.

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

Один
0.2635522849474877 0.10001114673002853 0.442971040143471
0.2986277338922876 0.7517642579959294 0.09150190333830721
0.8913610667753092 0.8898546572478708 0.25592546060133237

Инверсия
0.8913610667753092 0.8898546572478708 0.25592546060133237
0.26618513545092265 0.26573527978742995 0.07642644034471581
0.062426597261833985 0.06232109565941264 0.017923775508624545

Я был бы очень благодарен за любую помощь, так как не могу найти решение. Возможно, я где-то перепутал указатель или неправильно реализовал алгоритм.

1 Ответ

Я вижу две проблемы.

вы не изменяете значения, хранящиеся в матрице; вы просто изменяете значение value , а затем отбрасываете его. Вы хотите что-то вроде:

Кроме того, в этой строке:

Вы должны изменить = на -= . Алгоритм говорит: «вычтите A[u,j] * строку i из строки u». Вы просто заменяете значения в строке u на продукт.

Похожие вопросы:

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

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

Я успешно реализовал однопоточную программу в CUDA для исключения Гаусса и хотел бы добиться параллелизма. До этого момента параллельный код выглядит так: __global__ void ParallelGaussian(double* A).

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

я сделал свой проект, реализующий sift на доске beagle XM, и вышел из него OK. but для части презентации, я до сих пор не понимаю, почему разница Гаусса рассматривалась в sift, а не в выборе.

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

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

У меня уже есть простая факторизация (для целых чисел), но теперь я хочу реализовать ее для целых чисел Гаусса, но как это сделать? Спасибо!

Я попытался написать программу, которая делает LU split с использованием исключения Гаусса. Моя программа разбивает матрицу A на A=LR, где L, R-треугольные матрицы. Это прекрасно работает. Пусть.

Код метода Гаусса-Якоби в прикладной математике не выполняется успешно при компиляции, хотя ошибок нет: void main()< int a[3][4], i, j, k; float x,y,z; printf(Enter coeff of 3 equations and RHS :);.

Почему Гаусс? (100 способов решить систему уравннений)

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

Обо всем по порядку

Начнем с простого. Пусть задана система линейных уравнений третьего порядка:

$$display$$left < begina_<11>x_1 + a_<12>x_2 + a_<13>x_3 = b_1, a_<21>x_1 + a_<22>x_2 + a_<23>x_3 = b_2, a_<31>x_1 + a_<32>x_2 + a_<33>x_3 = b_3. end right.$$display$$

Метод Гаусса заключается в последовательном «уничтожении» слагаемых, находящихся ниже главной диагонали. На первом этапе первое уравнение умножается на $inline$ dfrac>> $inline$ и вычитается из второго (и аналогично умножается на $inline$ dfrac>> $inline$ и вычитается из третьего). То есть, после этого преобразования, получаем следующее:

$$display$$left < begina_<11>x_1 + a_<12>x_2 + a_<13>x_3 = b_1, a_<22>‘x_2 + a_<23>‘x_3 = b_2’, a_<32>‘x_2 + a_<33>‘x_3 = b_3’. end right.$$display$$

Теперь второе уравнение умножается на $inline$ dfrac‘>‘> $inline$ и вычитается из третьего:

$$display$$left < begina_<11>x_1 + a_<12>x_2 + a_<13>x_3 = b_1, a_<22>‘x_2 + a_<23>‘x_3 = b_2’, a_<33>»x_3 = b_3». end right.$$display$$

Получили довольно простую систему, из которой легко находится $inline$x_3$inline$, затем $inline$x_2$inline$ и $inline$x_1$inline$.

Внимательный читатель обязательно заметит: а что, если диагональные элементы равны нулю? Что же делать, если, например, $inline$a_ <11>= 0$inline$? Неужели знаменитый метод Гаусса на этом заканчивается?

Ничего страшного! Давайте найдем $inline$max|a_<1j>|$inline$ и поменяем местами $inline$j$inline$-ую и первую строку (не ограничивая общности, предположим, что $inline$max |a_<1j>| = a_<13>$inline$). Заметим, что случая, когда все $inline$a_<1j>=0$inline$ быть не может, так как в этом случае определитель матрицы коэффициентов обращается в ноль и решить систему не предоставляется возможным. Итак, после перестановки 3-го уравнение на первую строку, выполняем действия, описанные ранее.

Поиском максимального по модулю элемента можно заниматься на каждой итерации, то есть на $inline$k$inline$-ой итерации искать $inline$max |a_|$inline$, затем менять $inline$j$inline$-ую и $inline$k$inline$-ую строчки. Алгоритм, в которм осуществляется поиск максимального элемента в столбце, называется методом Гаусса с выбором главного элемента в столбце.

Есть и другой способ. Можно на $inline$k$inline$-ой итерации искать $inline$max |a_|$inline$, затем менять уже не строчки, а столбцы. Но при этом важно запоминать индексы меняющихся столбцов в какой-нибудь массив $inline$alpha$inline$ (чтобы потом восстановить точный порядок переменных).

Пример простого кода, реализующего данный алгоритм:

Почему Гаусс?

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

$$display$$ Delta = begin a_ <11>& a_ <12>& a_<13> a_ <21>& a_ <22>& a_ <23> a_ <31>& a_ <32>& a_<33> end, Delta_1 = begin b_1 & a_ <12>& a_<13> b_2 & a_ <22>& a_ <23> b_3 & a_ <32>& a_<33> end, $$display$$

$$display$$ Delta_2 = begin a_ <11>& b_1 & a_<13> a_ <21>& b_2 & a_ <23> a_ <31>& b_3 & a_<33> end, Delta_3 = begin a_ <11>& a_ <12>& b_1 a_ <21>& a_ <22>& b_2 a_ <31>& a_ <32>& b_3 end, $$display$$

Но вспомним — что такое определитель?

По определению, определитель матрицы $inline$A = (a_)$inline$ есть сумма

Программа решения СЛАУ по методу Гаусса

Введение

Метод Гаусса

Блок – схема метода Гаусса

Программа решения СЛАУ по методу Гаусса

var a: array [1..20,1..21] of real;

x: array [1..20] of real;

write(‘ Введи число неизвестных n=’); readln(n);

for j:=1 to n+1 do

if j=n+1 then writeln;

writeln(‘ Коэффициенты системы уравнений ‘);

for j:=1 to n+1 do

if j=n+1 then writeln(‘ a(‘,i,’,’,j,’)=’, a[i,j]:8:3)

for k:=1 to n-1 do

for i:=k+1 to n do

for j:=k to n+1 do

if j=k then aik:=a[i,k];

writeln( ‘ Корни системы:’);

for k:=n-1 downto 1 do

Метод Гаусса с выбором главного элемента
(максимального по модулю элемента по столбцу)

var a: array [1..20,1..21] of real;

x: array [1..20] of real;

write(‘ Введи число неизвестных n=’); readln(n);

for j:=1 to n+1 do

if j=n+1 then writeln;

writeln(‘ Коэффициенты системы уравнений ‘);

for j:=1 to n+1 do

if j=n+1 then writeln(‘ a(‘,i,’,’,j,’)=’, a[i,j]:8:3)

for k:=1 to n-1 do

for i:=k+1 to n do

if abs(a[i,k]) > max then

for j:=k to n+1 do

writeln(‘Шаг прямого хода К=’, k);

writeln(‘ Коэффициенты системы после перестановки уравнений’);

for j:=1 to n+1 do

if j=n+1 then writeln(‘ a(‘,i,’,’,j,’)=’, a[i,j]:8:3)

for i:=k+1 to n do

for j:=k to n+1 do

if j=k then aik:=a[i,k];

writeln(‘ К-ты системы после ‘, k , ‘-го шага преобразования’);

for j:=1 to n+1 do

if j=n+1 then writeln(‘ a(‘,i,’,’,j,’)=’, a[i,j]:8:3)

Программа решения СЛАУ по методу Гаусса

Введение

Метод Гаусса

Блок – схема метода Гаусса

Программа решения СЛАУ по методу Гаусса

var a: array [1..20,1..21] of real;

x: array [1..20] of real;

write(‘ Введи число неизвестных n=’); readln(n);

for j:=1 to n+1 do

if j=n+1 then writeln;

writeln(‘ Коэффициенты системы уравнений ‘);

for j:=1 to n+1 do

if j=n+1 then writeln(‘ a(‘,i,’,’,j,’)=’, a[i,j]:8:3)

for k:=1 to n-1 do

for i:=k+1 to n do

for j:=k to n+1 do

if j=k then aik:=a[i,k];

writeln( ‘ Корни системы:’);

for k:=n-1 downto 1 do

Метод Гаусса с выбором главного элемента
(максимального по модулю элемента по столбцу)

var a: array [1..20,1..21] of real;

x: array [1..20] of real;

write(‘ Введи число неизвестных n=’); readln(n);

for j:=1 to n+1 do

if j=n+1 then writeln;

writeln(‘ Коэффициенты системы уравнений ‘);

for j:=1 to n+1 do

if j=n+1 then writeln(‘ a(‘,i,’,’,j,’)=’, a[i,j]:8:3)

for k:=1 to n-1 do

for i:=k+1 to n do

if abs(a[i,k]) > max then

for j:=k to n+1 do

writeln(‘Шаг прямого хода К=’, k);

writeln(‘ Коэффициенты системы после перестановки уравнений’);

for j:=1 to n+1 do

if j=n+1 then writeln(‘ a(‘,i,’,’,j,’)=’, a[i,j]:8:3)

for i:=k+1 to n do

for j:=k to n+1 do

if j=k then aik:=a[i,k];

writeln(‘ К-ты системы после ‘, k , ‘-го шага преобразования’);

for j:=1 to n+1 do

if j=n+1 then writeln(‘ a(‘,i,’,’,j,’)=’, a[i,j]:8:3)

Решение системы линейных уравнений методом Гаусса

Дата добавления: 2014-05-02 ; просмотров: 4172 ; Нарушение авторских прав

Простейшие численные методы

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

,

где А – матрица m m, x = (x₁, x₂,…, x_m) T – искомый вектор, f = (f₁, f₂,…, f_m) T – заданный вектор. Предполагается, что определитель матрицы А отличен от нуля, так что решение x существует и единственно. Для большинства вычислительных задач характерным является большой порядок матрицы А. Систему (1) можно решать по крайней мере двумя способами: или по формулам Крамера, или методом Гаусса последовательного исключения неизвестных. При больших m первый способ, основанный на вычислении определителей, требует порядка m! Арифметических действий, а метод Гаусса – только О(m 3 ) действий. Поэтому метод Гаусса широко используется при численном решении задач линейной алгебры.

Методы численного решения системы линейных алгебраических уравнений делятся на две группы: прямые методы (Гаусса, Крамера) и итерационные методы. Итерационные методы состоят в том, что решение x системы находится как предел при n последовательных приближений x (n ) , где n – номер итерации. Обычно задается малое число и вычисления проводятся до тех пор, пока не будет выполнена оценка

.

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

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

Прямые методы не предполагают, что матрица А имеет какой-либо специальный вид и ее порядок не превышает 100.

Рассмотрим систему линейных алгебраических уравнений

, (1)

где А – матрица m m, x = (x₁, x₂,…, x_m) T – искомый вектор, f = (f₁, f₂,…, f_m) T – заданный вектор. Предполагается, что определитель матрицы А отличен от нуля, так что решение x существует и единственно.

Запишем систему (1) в развернутом виде

(2)

Метод Гаусса решения системы (2) состоит в последовательном исключении неизвестных x₁, x₂,…, x_m из этой системы. Предположим, что a₁₁<>0. Поделив первое уравнение на a₁₁ получим

, (3)

.

Рассмотрим теперь оставшиеся уравнения системы (2):

. (4)

Умножим (3) на a_i1 и вычтем полученное уравнение из i-го уравнения системы (4), i=2,…,m. В результате получим следующую систему уравнений:

. (6)

Матрица системы (5) имеет вид

.

Матрицы такой структуры принято обозначать так:

,

Где крестиками обозначены ненулевые элементы. В системе (5) неизвестное x₁ содержится только в первом уравнении, поэтому в дальнейшем достаточно иметь дело с укороченной системой уравнений

, (7)

,

.

Тем самым мы осуществили первый шаг метода Гаусса. Если , то из системы (7) совершенно аналогично можно исключить неизвестное x₂ и прийти к системе, эквивалентной (2) и имеющей матрицу следующей структуры:

.

При этом первое уравнение системы (5) остается без изменения.

Исключая таким же образом неизвестные x₃,x₄,…,x_m, придем окончательно к системе уравнений вида

. (9)

Содержит нули всюду ниже главной диагонали. Матрицы такого вида называются верхними треугольными матрицами.

Получение системы (8) составляет прямой ход метода Гаусса. Обратный ход заключается в нахождении неизвестных x₁,x₂,…,x_m из системы (8). Поскольку матрица имеет треугольный вид, можно последовательно, начиная с x_m, найти все неизвестные. Общие формулы обратного хода имеют вид

. (10)

При реализации в программе прямого хода метода Гаусса нет необходимости действовать с переменными x₁,x₂,…,x_m. Достаточно указать алгоритм, согласно которому исходная матрица А преобразуется к треугольному виду (9), и указать соответствующие преобразования правых частей системы. Получим эти общие формулы. Пусть реализованы первые k-1 шагов, т.е. уже исключены переменные x₁,x₂,…,x_k-1. Тогда имеем систему

Рассмотрим k-е уравнение этой системы

,

И предположим, что . Поделив обе части этого уравнения на , получим

, (12)

.

.

Далее, умножим уравнение (12) на и вычтем полученное соотношение из i-го уравнения системы (11), где i=k+1,k+2,…,m. В результате последняя группа уравнений системы (11) примет вид

.

Таким образом, в прямом ходе метода Гаусса коэффициенты уравнений преобразуются по следующему правилу:

,

. (13)

.

Вычисление правых частей системы (8) осуществляются по формулам

(15)

. (16)

Коэффициенты c_ij и правые части y_i, i=1,2. m, j=i+1,i+2,…, m, хранятся в памяти и используются при осуществлении обратного хода по формулам (10).

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

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

Листинг 15.1. Метод Гаусса

public static void Gauss(float[,] A, float[] B,