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

Введение

Карл Давид Тольме Рунге (30 августа 1856 - 3 января 1927) - выдающийся немецкий математик, физик и спектроскопист. Обучался в Берлинском университете, где получил степень PhD, являлся профессором математики в Ганноверском университете, а также главой кафедры прикладной математики в Гёттингене. [1]

в 1901 году Карл открыл "Феномен Рунге" - в численном анализе эффект нежелательных колебаний, возникающий при интерполяции полиномами высоких степеней - о котором пойдёт речь в данной статье. [2]

Но прежде, чем мы окунёмся глубже в изучение данного феномена, давайте поговорим об интерполяционном многочлене Лагранжа, на примере которого мы и разберём Феномен Рунге.

Интерполяционный многочлен Лагранжа

Полином Лагранжа - это математическая функция, позволяющая записать полином n-степени, который будет соединять все заданные точки из набора значений, полученных опытным путём или методом случайной выборки. Многочлен в форме Лагранжа в явном виде содержит значения функций в узлах интерполяции, поэтому он удобен, когда значения функций меняются, а узлы интерполяции неизменны. Число арифметических операции, необходимых для построения многочлена Лагранжа, пропорционально и является наименьшим для всех форм записи. [3]

Полином Лагранжа в общем виде выглядит следующим образом:

Привет, Хабр! Это Саша Баулин из МТС Диджитал. Представьте, что вы решили построить дом своей мечты и активно погрузились в процесс: покупку земли, поиск строительной бригады, укладку фундамента и внутреннюю отделку. Через пару лет на строительство потрачены десятки миллионов рублей, дом почти готов. Но в самом конце оказывается, что черепица в бюджет не вписывается. И теперь дом придется разбирать.

Примерно в такой ситуации оказалось агентство NASA со своим проектом лунохода VIPER. Проект очень дорогой, для науки важный… мог бы быть. Подробности — под катом.

Алгоритм

Привет, Хабр! Я Андрей Соколов, инженер-программист в группе разработки математических библиотек. Месяц назад моя коллега Валерия запустила цикл статей про матричные расширения, ускоряющие операции над матрицами. Вы уже смогли узнать, что они делают и какие существуют, какие из них разрабатываются для открытой архитектуры RISC-V.

В заключительной статье цикла разберем пример использования матричного расширения T-Head под RISC-V для реализации алгоритма матричного умножения. Сначала кратко рассмотрим наивную скалярную реализацию и блочный вариант алгоритма. Затем реализуем аналогичный вариант с использованием матричного расширения — как для квадратных матриц, так и матриц произвольного размера. Второй случай интересен тем, что возникает необходимость обработки так называемых «хвостов» — блоков неправильной конфигурации. В заключение немного расскажу, какие идеи можно использовать для дальнейшей оптимизации матричного умножения, и поделюсь полезными ссылками.

Статья не показывает пошаговую оптимизацию умножения матриц для достижения максимума FLOPS и не учит, как писать вычислительные ядра на ассемблере. Она демонстрирует использование матричного расширения и основные идеи оптимизации матричного умножения. Постарался описать все простыми словами, с иллюстрациями и небольшими вставками кода.

Звездное скопление Омега Центавра (Рис.1) с массой в 4 миллиона солнечных имеет радиус около 90 световых. 10 июля 2024 года в журнале Nature была опубликована сенсационная статья об открытии в этом скоплении черной дыры с массой в 8200 раз больше массы Солнца. Главными свидетелями существования этого невидимого объекта оказались быстрые звезды, которые без гравитационного поля массивной дыры должны были покинуть скопление очень быстро - в течение тысячи лет.

Тема обсуждения

В недавно опубликованном здесь материале о космологической модели Неустойчивой решётки (НР), то есть модели Вселенной без Большого взрыва (БВ), не обсуждались такие доводы в пользу БВ, как космологическое красное смещение, наличие космологического горизонта и реликтового микроволнового излучения, которых в квазистационарной Вселенной быть, казалось бы, не должно. «Старение фотонов», объясняющее красное смещение света и наблюдаемое в некоторых случаях аномальное торможение тел передачей кинетической энергии от тел и фотонов флуктуациям вакуума, подвергается сомнениям после моделирования обстоятельств торможения аппаратов «Пионер», доказывающего тепловую природу торможения [1]. Наконец, и старение фотонов, и гравитационная гипотеза «покраснения» выглядят не совместимыми с динамикой эволюции сверхновых, которая коррелирует с их красным смещением, а в рамках этих двух гипотез, вроде, не должна бы.

Первый довод можно попытаться оспорить, заявив, что бесконечно протяжённая Вселенная не обязана быть стационарной, поскольку не придумано пока ещё запретов на её расширение (с соответствующим красным смещением) по каким‑нибудь причинам. Другое дело, что неизвестная причина расширения — это на данный момент «излишняя сущность», а «бритва Оккама» настойчиво рекомендует таковых избегать при «измышлении гипотез». Удастся ли вписать красное смещение и т. п. в модель НР, не прибегая, по возможности, к новым сущностям?

Рассмотрим гравитационную гипотезу более внимательно.

Основной посыл статьи – демонстрация возможности детерминирования динамических свойств технологических параметров, описываемых решётчатыми функциями, и возможности прогнозирования изменения значений этих параметров, применяя простые, а оттого высокопроизводительные вычислительные инструменты.

Статья не претендует на научную точность, уникальность и оригинальность. Доступна в формате Jupyter Notebook и PDF по ссылке – https://gitflic.ru/project/56h/tde

Лет 20 назад по телевизору довольно часто обсуждалась тема, что человечество размножается очень быстро. И что с такими темпами, нас скоро накроет волна перенаселения планеты и придется убивать друг друга в борьбе за товары. Однако, взрывного роста ожидать не следует. И темп приумножения населения планеты постепенно снижается. О его пределах и коллизиях на пути рассказано в прогнозе ООН.

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

Теперь мы будем исследовать другую задачу. Дана система нелинейных уравнений. Необходимо разделить систему на две подсистемы - "уравнения" и "подстановки" с помощью алгоритма Тарьяна. Подсистема подстановок должна быть формально вычислимой. Подставив уравнения второй категории в первую, получим систему меньшей размерности, которую будет проще решить численными методами.

Однажды, выполнив в Гугле запрос "Three body problem" ("Задача трёх тел"), я был просто поражен - первая страница результатов состояла только из ссылок на роман китайского писателя-фантаста Лю Цысиня с соответствующим названием, а также на телесериал, снятый по этому роману, т.е. ссылок на собственно задачу трёх тел не было вообще! Мне это показалось удивительным и несправедливым, поскольку сама по себе задача трёх тел тоже может выглядеть увлекательной в популярном изложении. В этой публикации я постарался привести некоторые доказательства этого утверждения.

Всем привет! Я тут недавно начал разбираться в одной очень интересной теме, связанной с обработкой цифровой информации. Объектом моего исследования стали помехоустойчивые коды. Когда я был студентом, я даже писал студенческую научную статью, в которой представил код на Си для кодирования информации кодом Хэмминга на Arduino. Только вот коды Хемминга вряд ли можно применить в каких‑нибудь сложных каналах связи по типу WiFi или LTE, поэтому я начал изучать другие коды. Немного погуглив, я понял что мейнстримом среди помехоустойчивых кодов являются LDPC коды.

На Хабре была статья на тему помехоустойчивого кодирования и LDPC кодов. В ней автор очень круто описал основные принципы обработки информации, закодированной LDPC кодом, и даже привел пример декодирования методом SPA и некоторые мысли о том, как это дело можно оптимизировать. Я решил привнести свою лепту и подготовил свою небольшую статью в которой расскажу про кодирование информации на примере метода Ричардсона‑Урбанке (Richardson — Urbanke method), а также рассмотрю вариант декодирования информации методом minsum и различные способы оптимизации этого метода.

Рекомендации для ЛЛ: не читать, минусовать.
Рекомендации для Хабра: какие‑то глупости от нейросети, не читать, минусовать.

Предисловие

До того, как я начал писать эту статью, я думал что Lockheed SR-71 был отдельным, уникальным проектом. Я ошибался, все было не так.

В процессе решения некоторой задачи, я наткнулся на одно интересное свойство триангуляции Делоне, которое мне не удалось загуглить, как и его применение к решению разных задач. Я уверен, что не являюсь его первооткрывателем, но оно, по крайней мере, не является широко известным. Поэтому я решил написать о нем статью.

Свойство: Если какой‑то отрезок AB не включен в триангуляцию Делоне, то существует путь из A в B по отрезкам из триангуляции, такой что каждый из отрезков в нем не длиннее |AB|. На картинке выше отсутствующий отрезок показан красным цветом, а путь — зеленым цветом.

Дальше в статье я приведу пример его использования в задачах, а также формальное его доказательство.

Если вам известно более красивое доказательство этого свойства, или вы его где‑то видели — поделитесь, пожалуйста, в комментариях. Также буду благодарен, если вы поделитесь другими решениями для приведенных в статье задач или аналогичными задачами.

Поступила задача выполнения кластеризации множества товаров, по их размерам (двумерная плоскость). Значения распределения: ширина и высота.

После изучения вопроса, было найдено несколько подходящих алгоритмов, одним из самых распространенных оказался алгоритм под названием K-means, а так же его вариация K-means++. Плюсы, в отличии от классики, подошли более разумно к подбору начальных точек опоры, калибрующихся итерационно, до момента идентичности нескольких последовательных результатов.

Сегодняшний разговор пойдет о том, как правильно следует устанавливать 64-битную Windows 11 поверх ранее установленной 64-битной операционной системы Windows 7, 8, 10 или 11. Не пропагандирую переход на Windows 11, — выбор за вами, если это вам не нужно, ради бога, — но давайте поможем тем кто хочет это сделать, но встречается с разными сложностями на пути. Хотя при этом, заметка в целом полезна и тем, кто использует, и планирует далее использовать устаревшие системы, — рассказанный мной способ установки ОС «поверх» или «апгрейд» в целом общий для всех версий Windows, я лишь буду отмечать тонкости ранее мне не встречающиеся. Чего еще не будет в этой статье, так это вопросов совместимости с ПО и железом, — такое коротко и обобщенно не описать, решать нужно конкретно поставленную задачу. Обновлять ОС на совсем уж старом железе, наверное, нецелесообразно, а способов заставить работать древний софт на современных ОС известно много, но они тоже подбираются под нужды.

Собственно, начать об обновлении ОС я хочу с того, что Microsoft всегда имеет «матрицу обновляемости» (upgrade matrix) и четкие правила того, что на что может быть обновлено. Начнем с матрицы (а как иначе, Нео?). В любой версии и издании Windows в папке C:\Windows\servicing\Editions лежит файл UpgradeMatrix.xml, в котором четко прописано, с каких версий и изданий вы можете выполнить обновление на данную систему. Для ОС, которая в ISO образе, или на установочной флешке, этот файл лежит внутри install.wim, его проще всего открыть 7zip архиватором и посмотреть, если есть интерес. Разбирать его детально я сегодня не буду, это скучная задача, поговорим о сложностях, возникающих при обновлении ОС.

Матричное расширение ISA CPU… Что это и что оно делает? Уже из названия понятно, что это расширение позволяет ускорять операции над матрицами на CPU. Но задумывались ли вы когда-нибудь, какие они бывают, когда появились, кто и как их создает?

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

Матричные расширения появились не так давно — чуть более трех лет назад. Несмотря на это, они есть у каждой уважающей себя процессорной архитектуры, в том числе и у относительно молодой открытой RISC-V. Почему их так много и чем они отличаются? Поддерживаются ли разреженные матрицы? Об этом и многом другом вы узнаете из статьи. Приготовьтесь, будет интересно и (спойлер!) без многоэтажных формул. 

статья представляет подробное описание реализации функции Стьюдента (Student's t-distribution) в языке программирования Scala с использованием алгоритма ACM395 и ACM209. Функция Стьюдента является важным инструментом в статистике для вычисления критических значений t-статистики и вероятностей в t-распределении.

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

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

Стандартная модель физики частиц хорошо объясняет взаимодействие между основными элементами материи. Но она не идеальна. Она с трудом объясняет тёмную материю. Тёмная материя составляет большую часть материи во Вселенной, но мы не знаем, что это такое.

Стандартная модель утверждает, что, чем бы ни была тёмная материя, она не может взаимодействовать сама с собой. Новое исследование, возможно, перевернёт это представление.

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