Форум программистов, компьютерный форум, киберфорум
Scilab
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.54/13: Рейтинг темы: голосов - 13, средняя оценка - 4.54
Эксперт С++
2137 / 1568 / 239
Регистрация: 29.05.2011
Сообщений: 3,261
1

Решение разреженных систем

08.08.2011, 18:12. Просмотров 2411. Ответов 7

Возможно кому-нибудь будет полезно.
Программа для решения системы большого порядка из этого сообщения.
Для получения файлов a1.txt, a2.txt, b.txt написал небольшой конвертер на python, если надо, могу и его показать.
Код
// матрица представлена двумя файлами.
// в первом в каждой строке 2 числа, разделённые пробелом - координаты элемента
a1 = read('/tmp/matrix/a1.txt', 5920, 2);

// во втором в каждой строке значение, записываемое в элемент матрицы
// по кооржинатам из соответствующей строки первого файла
a2 = read('/tmp/matrix/a2.txt', 1, 5920);

// вектор-столбец свободных членов
b = read('/tmp/matrix/b.txt', 3638, 1);

// формирование разреженной матрицы
sp = sparse(a1, a2);
// Следующие три строки можно раскомментировать,
// чтобы получить однозначное решение (так как ранг исходной матрицы 3635)
//sp(1694,1694) = 1;
//sp(1721,1721) = 1;
//sp(1797,1797) = 1;
// LU-разложение матрицы
[hand,rk] = lufact(sp)
// решение системы
x = lusolve(hand, b);
// освобождение памяти 
ludel(hand)

// проверка решения
b_test = sp * x;

x_file = '/tmp/matrix/x.txt';
b_test_file = '/tmp/matrix/b_test.txt';
mdelete(x_file);
mdelete(b_test_file);
// сохранение решений
write(x_file, x);
// сохранение проверочных коэффициентов
write(b_test_file, b_test);
3
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.08.2011, 18:12
Ответы с готовыми решениями:

Решение систем уравнений графически
Возникла трудность в графическом решении систем уравнений, чтобы построить график, необходимо...

Решение разреженных СЛАУ
Здравствуйте, вопрос в следующем: есть большая несимметричная разреженная матрица, состоящая из 7...

Решение систем
Не могу почему-то в в маткаде решить обычную систему. Вот листинг. Почему-то после знака "=" само...

Решение систем
Помогите, пожалуйста, решить систему нелинейных алгебраических уранений методом Ньютона на Delphi....

7
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
09.08.2011, 10:55 2
Кстати есть замечание по поводу строк 1694,1721,1797 матрицы. Вообще матпакет может решать и такие системы, ранг матрицы коэффициентов которой не совпадает с количеством переменных. Так что, в принципе, можно оставить их нулевыми.

Добавлено через 2 минуты
И конечно было бы не плохо увидеть твой конвертор.

Добавлено через 19 минут
Думаю написать похожий конвертор только на С++. Все-таки плюсы роднее.

Добавлено через 5 минут
Кстати, зачем использовал конвертор для файла b.txt?
0
Эксперт С++
2137 / 1568 / 239
Регистрация: 29.05.2011
Сообщений: 3,261
09.08.2011, 11:46  [ТС] 3
Цитата Сообщение от hello19 Посмотреть сообщение
Кстати есть замечание по поводу строк 1694,1721,1797 матрицы. Вообще матпакет может решать и такие системы, ранг матрицы коэффициентов которой не совпадает с количеством переменных. Так что, в принципе, можно оставить их нулевыми.
Да, конечно. Он решает и с нулями. Но как известно, количество решений системы при этом бесконечно. Поскольку в векторе b в этих строках 0, то запись единицы в диагональный элемент гарантирует получение 0 в решении в соответствующем элементе, то есть запись единицы используется только с целью получить вполне определённое решение. И с учётом нулей в этих строках в вектор-столбце b, запись ненулевого значения в эти диагональные элементы эквивалентна вычёркиванию соответствующей строки и столбца.
Что качается строк 1694 и 1721 то их можно безболезненно удалить вместе со столбцами, так как и столбцы с этими номерами нулевые, то есть x[1694] и x[1721] сами по себе и никак не связаны с остальными переменными. А вот в столбце 1797 есть ненулевой элемент, так что значение x[1797] связано, по-меньшей мере, ещё с одной переменной.

Цитата Сообщение от hello19 Посмотреть сообщение
Кстати, зачем использовал конвертор для файла b.txt?
Во-первых запятые надо было в точки преобразовать, во-вторых избавится от BOM-сигнатуры в начале файла в кодировке UTF-8. И то и другое можно сделать с помощью текстового редактора, но раз уж всё-равно скрипт запускать...

Цитата Сообщение от hello19 Посмотреть сообщение
И конечно было бы не плохо увидеть твой конвертор.
Да, немного позже. Пока же прикрепляю уже преобразованные данные, для истории

Цитата Сообщение от hello19 Посмотреть сообщение
Думаю написать похожий конвертор только на С++. Все-таки плюсы роднее.
Плюсы, конечно, очень мощный инструмент, и владею я им гораздо лучше питона, но здесь эта мощь не нужна.
0
Вложения
Тип файла: 7z test_data.7z (24.4 Кб, 26 просмотров)
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
09.08.2011, 12:21 4
Что же касается наличия запятых - уже разобрался..

Прогаю на плюсах, потому что все-таки скорость нужна. Да и потом другие языки не очень то знаю, разве что чистый С))

Добавлено через 20 минут
Забавно то, что система решалась неправильно с использованием linsolve.
0
Эксперт С++
2137 / 1568 / 239
Регистрация: 29.05.2011
Сообщений: 3,261
10.08.2011, 13:01  [ТС] 5
В общем вот этот конвертер. Возможно питон-гуру могли бы написать красивее, я уж как сумел
Первая половина, собственно, и преобразует коэффициенты матрицы, вторая же заодно уж и вектор b подправляет.
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/usr/bin/python
# -*- coding: utf-8 -*-
import re
f = open('/tmp/matrix/СЛУ1 - Коэффициенты.txt', 'r')
w1 = open('/tmp/matrix/a1.txt', 'w')
w2 = open('/tmp/matrix/a2.txt', 'w')
p = re.compile(r'\(\s*([^;]+)\s*;\s*([^\)]+)\s*\)')
cnt = 0
newlines = 0
for line in f:
    cnt += 1
    for m in p.finditer(line.replace(',', '.')):
        (x, y) = m.group(1, 2)
        w1.write(str(cnt)+' '+x+'\n')
        w2.write(y+'\n')
        newlines += 1
print 'lines_src:', cnt
print 'lines_dst:', newlines
w2.close()
w1.close()
f.close()
 
f = open('/tmp/matrix/СЛУ1 - Свободные члены.txt', 'r')
w3 = open('/tmp/matrix/b.txt', 'w')
num_ptrn = r'[\d\-eE.]+'
p = re.compile('(' + num_ptrn + ')')
newlines = 0
for line in f:
    for m in p.finditer(line.replace(',', '.')):
        w3.write(m.group(1)+'\n')
        newlines += 1
w3.close()
f.close()
print 'lines_B:', newlines
1
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
10.08.2011, 13:09 6
У меня уже есть аналог на С++))) Всерно спасибо!
0
3 / 4 / 1
Регистрация: 13.07.2011
Сообщений: 313
10.12.2011, 15:18 7
У меня есть матрица порядка 100000. Она - сильно разреженная. Как можно найти ее собственные значения?
0
Эксперт С++
2137 / 1568 / 239
Регистрация: 29.05.2011
Сообщений: 3,261
11.12.2011, 16:20  [ТС] 8
Поверхностный поиск показывает, что справиться с такой проблемой может помочь "ARnoldi PACKage". Но, с первого взгляда, там всё очень непросто. Как выдастся относительно свободный денёк — попробую разобраться.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.12.2011, 16:20

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Решение систем
Решение систем матричным методом, Методом Гаусса и Крамера. Мне бы хоть одним, самым простым...

Решение систем уравнений
Здравствуйте. У меня к вам такой вопрос допустим у нас есть даны координаты центра кругов и радиусы...

Решение систем уравнений
Доброго времени суток, кто бы смог помочь с решением данных систем?

Решение систем уравнений
как в маткаде решаются подобные систему уравнений ? под знаком системы y=ln(x+100)^2...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.