Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 35 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 17 ноя 2019, 04:26 
Не в сети
Одарённый
Зарегистрирован:
07 ноя 2015, 02:22
Сообщений: 130
Cпасибо сказано: 41
Спасибо получено:
2 раз в 2 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Какова сложность если n элементов в матрице 1хn


думаю n^2

получается одно уравнение и несколько неизвестных

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 17 ноя 2019, 04:32 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5232
Cпасибо сказано: 83
Спасибо получено:
1131 раз в 1031 сообщениях
Очков репутации: 232

Добавить очки репутацииУменьшить очки репутации
Вы не думаете, вы гадаете. Это не очень продуктивно

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
K1b0rg
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 17 ноя 2019, 04:44 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5232
Cпасибо сказано: 83
Спасибо получено:
1131 раз в 1031 сообщениях
Очков репутации: 232

Добавить очки репутацииУменьшить очки репутации
n элементов в матрице nxn. Как матрица будет выглядеть? Как решить такое уравнение? Сколько операций придется сделать?.
n элементов в матрице mxm. В матрице нет нулевых элементов. Какова сложность? Чему примерно равно m?

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
K1b0rg
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 17 ноя 2019, 05:18 
Не в сети
Одарённый
Зарегистрирован:
07 ноя 2015, 02:22
Сообщений: 130
Cпасибо сказано: 41
Спасибо получено:
2 раз в 2 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Какова сложность если n элементов в матрице 1хn


Тогда O(n) просто пройти все ряды в первой строке.

Максимум в ряде искать не надо, это уже первый элемент
строки местами менять не надо потому что максимум есть
элементы ниже первого в том же столбце менять на нули не надо
по диагонали для треугольника ничего делать не надо

swan писал(а):
n элементов в матрице nxn. Как матрица будет выглядеть? Как решить такое уравнение? Сколько операций придется сделать?.


n элементов в матрице nxn значит например: 3 элемента в матрице 3x3:
[math]\begin{pmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}[/math]

например
[math]\begin{pmatrix} 1x{_1} & 2{x_2} & 3{x_3} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} * \begin{pmatrix} 5 \\ 0 \\ 0 \end{pmatrix}[/math]
[math]x_1 = 5-2{x_2}-3{x_3}[/math]
остальные x2=x2..

Тут матрица квадратная поэтому время O(n^3)

swan писал(а):
n элементов в матрице mxm. В матрице нет нулевых элементов. Какова сложность? Чему примерно равно m?


снова квадратная матрица значит O(m^3)
[math]m = \sqrt{n}[/math]

алгоритм https://martin-thoma.com/solving-linear-equations-with-gaussian-elimination/ смотрел

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 18 ноя 2019, 10:48 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5232
Cпасибо сказано: 83
Спасибо получено:
1131 раз в 1031 сообщениях
Очков репутации: 232

Добавить очки репутацииУменьшить очки репутации
K1b0rg писал(а):
n элементов в матрице nxn значит например: 3 элемента в матрице 3x3:
[math]\begin{pmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}[/math]

например
[math]\begin{pmatrix} 1x{_1} & 2{x_2} & 3{x_3} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} * \begin{pmatrix} 5 \\ 0 \\ 0 \end{pmatrix}[/math]
[math]x_1 = 5-2{x_2}-3{x_3}[/math]
остальные x2=x2..

Тут матрица квадратная поэтому время O(n^3)


Я вообще подразумевал, что элементы случайно по матрице раскиданы. Но так даже лучше получилось.
По факту вы написали матрицу 1хn, дополнив ничего не значащими нулями. Но время до n^3 увеличилось. Потрясающе!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 18 ноя 2019, 12:19 
Не в сети
Одарённый
Зарегистрирован:
07 ноя 2015, 02:22
Сообщений: 130
Cпасибо сказано: 41
Спасибо получено:
2 раз в 2 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
K1b0rg писал(а):
n элементов в матрице nxn значит например: 3 элемента в матрице 3x3:
[math]\begin{pmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}[/math]

например
[math]\begin{pmatrix} 1x{_1} & 2{x_2} & 3{x_3} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} * \begin{pmatrix} 5 \\ 0 \\ 0 \end{pmatrix}[/math]
[math]x_1 = 5-2{x_2}-3{x_3}[/math]
остальные x2=x2..

Тут матрица квадратная поэтому время O(n^3)


Я вообще подразумевал, что элементы случайно по матрице раскиданы. Но так даже лучше получилось.
По факту вы написали матрицу 1хn, дополнив ничего не значащими нулями. Но время до n^3 увеличилось. Потрясающе!


Размер сбил с толку, значит O(n).

Допустим такая матрица: [math]\begin{pmatrix} {x_1} & 0 & 3{x_3} \\ 0 & 2{x_2} & 0 \\ 0 & 0 & 0 \end{pmatrix}[/math] тут же никаких операций кроме как просто пройтись по всем элементам и прочитать значение за O(n) нету.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 18 ноя 2019, 12:21 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5232
Cпасибо сказано: 83
Спасибо получено:
1131 раз в 1031 сообщениях
Очков репутации: 232

Добавить очки репутацииУменьшить очки репутации
Вот и я о том же )))

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
K1b0rg
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 18 ноя 2019, 16:56 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
15 мар 2016, 15:08
Сообщений: 5875
Cпасибо сказано: 69
Спасибо получено:
921 раз в 875 сообщениях
Очков репутации: 168

Добавить очки репутацииУменьшить очки репутации
K1b0rg писал(а):
Значит это ответ или они что-то другое хотели?

Для того, чтобы понять, что "они хотели", надо уметь либо дословно переписывать условие задания, либо уметь его фотографировать и выкладывать сюда (желательно не в перевёрнутом виде).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 18 ноя 2019, 21:53 
Не в сети
Одарённый
Зарегистрирован:
07 ноя 2015, 02:22
Сообщений: 130
Cпасибо сказано: 41
Спасибо получено:
2 раз в 2 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
окей

swan писал(а):
Вот и я о том же )))


Да точно) всё правильно ответил 10/10. спасибо большое

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Время выполнения метода Гаусса
СообщениеДобавлено: 22 ноя 2019, 15:08 
Не в сети
Одарённый
Зарегистрирован:
07 ноя 2015, 02:22
Сообщений: 130
Cпасибо сказано: 41
Спасибо получено:
2 раз в 2 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Снова похожий вопрос, не пойму какой ответ
Q - ортогональная квадратная матрица размера >= 2x2 ( n > 1)
Вопрос:
Какая временная сложность у [math]Qx=b[/math]? (Метод решения может быть и не Гаусса)
Варианты:
[math]O(n)[/math] Да/Нет
[math]O(n^2)[/math] Да/Нет

Знаю что есть у неё свойство [math]Q^{T}= Q^{-1}[/math] и значит [math]Q \cdot Q^T = E[/math]. Знаю метод Гаусса, разложение Холецкого и обратную перестановку только не вижу как эти методы могут помочь в решении если матрица ортогональна. Думаю что решается она за O(n^3) и вопросы с подвохом, оба ответа не правильные. Была бы треугольная то за O(n^2), диагональная или с n элементами за O(n) а так не знаю..

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу Пред.  1, 2, 3, 4  След.  Страница 3 из 4 [ Сообщений: 35 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Применение метода гаусса

в форуме Линейная и Абстрактная алгебра

helpmeplz

1

243

01 ноя 2012, 22:18

Использование метода Гаусса

в форуме Линейная и Абстрактная алгебра

n476

0

152

27 ноя 2016, 14:34

Метод Гаусса для итерационного метода Ньютона

в форуме Численные методы

object1

3

437

04 июн 2015, 18:49

Сравнительная характеристика методов Гаусса и метода Крамера

в форуме Линейная и Абстрактная алгебра

1243

5

1212

18 сен 2012, 17:49

Порядок выполнения интегрирования и дифференцирования

в форуме Дифференциальное исчисление

kare

2

65

04 ноя 2019, 00:58

помогите с методикой выполнения задачи

в форуме Алгебра

olechka147

4

1069

21 сен 2011, 22:27

Формула для вычисления процента выполнения программы

в форуме Информатика и Компьютерные науки

hammer46

0

634

13 июл 2013, 15:02

Найти вероятность своевременного выполнения задания

в форуме Теория вероятностей

elena8585

11

1874

13 июн 2012, 19:21

показатели динамики и выполнения плана по выпуску продукции

в форуме Экономика и Финансы

maryana

2

701

13 янв 2011, 22:15

Выбор метода

в форуме Исследование операций и Задачи оптимизации

Ivann

0

207

24 окт 2015, 15:29


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2020 MathHelpPlanet.com. All rights reserved