Решение системы уравнений с N>=10000 переменными

@kiborgdelto · Регистрация: 23.03.2011

Студворк — интернет-сервис помощи студентам

Здравствуйте
есть такая проблема: необходимо решить систему линейных алгеброических уравнений, проблема состоит в том что число уравнений и переменных в этой системе от 10000, а т.к. решить нужно не менее 10 подобных систем (а вообще то желательно не менее 100), то для решения требуется довольно много времени
можно ли как то сократить время решения системы?
используется метод Гаусса-Жордана
вот код самого метода (матрица А это матрица коэфицентов с присоединёным к ней вектором правой части)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void gauss_jordan(double **A, int N, double *reshenie)
{
    
for(int q2=0;q2<N;q2++)
    {
int m=0;
double max=0,p;
    
    // делим строку на элемент стоящий на главной диагонали при условии что этот элемент не равен 1
    if(A[q2][q2]!=1)    for(int i=N;i>q2-1;i--)A[q2][i]=A[q2][i]/A[q2][q2];
 
// вычитаем строку с которой работаем из остальных строк( вычитаем с конца, для того чтобы не обнулять элементы под и над элементом стоящим на главной диагонали)
    for (int i=0;i<N;i++)
            if (i!=q2&&A[i][q2]!=0)for(int j=N;j>q2-1;j--)A[i][j]=A[i][j]-A[q2][j]*A[i][q2];
}
for (int i=0;i<N;i++) reshenie1[i][s1]=A[i][N];
}

матрица коэфицентов выглядит так (N=16)
[]http://pixs.ru/showimage/Bezimyanni_6833920_11776237.jpg[/]

большая часть матрицы нули, в каждой строке не больше 4-х коэфицентов

@IrineK · 20.04.2014, 18:19

Разреженные матрицы

@AndrSlav · 21.04.2014, 00:12

Самый простой -метод Якоби http://ru.wikipedia.org/wiki/%... 0%B1%D0%B8 .
А если матрица ленточная, то надо хранить только сами ленты со значениями.

@kiborgdelto · 21.04.2014, 03:20 **[ТС]**

метод якоби точно не подходит (во первых он приближённый а не точный, что не есть хорошо, а во вторых количество операций будет больше чем в методе гаусса-жордана и в третьих не учитывается разряженность матрицы)
матрица не ленточная, известно только что в каждой строке не более 4-х коэфицентов отличных от 0, какие конкретно коэфиценты заранее неизвестно (не факт что даже главная диагональ будет не нулевой), всё зависит от заданной области (решается задача дирихле в произвольной области)

@AndrSlav · 21.04.2014, 23:32

kiborgdelto,
Насчет количества итераций- как Вы посчитали?
Я не правильно выразился насчет ленточной, не знаю как правильно называются, но такие как у Вас в примере я как раз решаю методом Гаусса-Зейделя, храню только элементы (учет разреженности, в частности, для Вашего примера достаточно хранить матрицу коэф-ов не N на N, а 5 на N).
Задачи аэрогидродинамики все считают итерационными методами, а там как раз матрицы похожие на Ваши.
p.s. Да и ошибка в процессе исключения Гаусса накопится.

Новые блоги и статьи Все статьи Все блоги /
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	20.04.2014, 18:19
	Разреженные матрицы 0

@AndrSlav 71 / 59 / 14 Регистрация: 20.12.2013 Сообщений: 732
	21.04.2014, 00:12
	Самый простой -метод Якоби http://ru.wikipedia.org/wiki/%... 0%B1%D0%B8 . А если матрица ленточная, то надо хранить только сами ленты со значениями. 0

@kiborgdelto 76 / 78 / 41 Регистрация: 23.03.2011 Сообщений: 148
	21.04.2014, 03:20 [ТС]
	метод якоби точно не подходит (во первых он приближённый а не точный, что не есть хорошо, а во вторых количество операций будет больше чем в методе гаусса-жордана и в третьих не учитывается разряженность матрицы) матрица не ленточная, известно только что в каждой строке не более 4-х коэфицентов отличных от 0, какие конкретно коэфиценты заранее неизвестно (не факт что даже главная диагональ будет не нулевой), всё зависит от заданной области (решается задача дирихле в произвольной области) 0

@AndrSlav 71 / 59 / 14 Регистрация: 20.12.2013 Сообщений: 732
	21.04.2014, 23:32
	kiborgdelto, Насчет количества итераций- как Вы посчитали? Я не правильно выразился насчет ленточной, не знаю как правильно называются, но такие как у Вас в примере я как раз решаю методом Гаусса-Зейделя, храню только элементы (учет разреженности, в частности, для Вашего примера достаточно хранить матрицу коэф-ов не N на N, а 5 на N). Задачи аэрогидродинамики все считают итерационными методами, а там как раз матрицы похожие на Ваши. p.s. Да и ошибка в процессе исключения Гаусса накопится. 0