Quasi-Monte Carlo method (original) (raw)
준몬테카를로 방법(Quasi-Monte Carlo method)은 저불일치 수열(Low-discrepancy sequence)을 사용해 몬테카를로 방법을 개선한 수치적분이다. 준몬테카를로 방법에서는 몬테카를로 방법의 의사난수 대신 등의 저불일치 수열을 사용한다.
| Property | Value |
|---|---|
| dbo:abstract | In numerical analysis, the quasi-Monte Carlo method is a method for numerical integration and solving some other problems using low-discrepancy sequences (also called quasi-random sequences or sub-random sequences). This is in contrast to the regular Monte Carlo method or Monte Carlo integration, which are based on sequences of pseudorandom numbers. Monte Carlo and quasi-Monte Carlo methods are stated in a similar way.The problem is to approximate the integral of a function f as the average of the function evaluated at a set of points x1, ..., xN: Since we are integrating over the s-dimensional unit cube, each xi is a vector of s elements. The difference between quasi-Monte Carlo and Monte Carlo is the way the xi are chosen. Quasi-Monte Carlo uses a low-discrepancy sequence such as the Halton sequence, the Sobol sequence, or the Faure sequence, whereas Monte Carlo uses a pseudorandom sequence. The advantage of using low-discrepancy sequences is a faster rate of convergence. Quasi-Monte Carlo has a rate of convergence close to O(1/N), whereas the rate for the Monte Carlo method is O(N−0.5). The Quasi-Monte Carlo method recently became popular in the area of mathematical finance or computational finance. In these areas, high-dimensional numerical integrals, where the integral should be evaluated within a threshold ε, occur frequently. Hence, the Monte Carlo method and the quasi-Monte Carlo method are beneficial in these situations. (en) En analyse numérique, la méthode de quasi-Monte-Carlo est une méthode d'intégration numérique et la résolution de problèmes numériques par l'utilisation de suites à discrépance faible. Elle s'oppose donc à la méthode de Monte-Carlo qui utilise des suites de nombres pseudo-aléatoires. Les méthodes de Monte-Carlo et quasi-Monte-Carlo se basent sur le même problème : l'approximation de l'intégrale d'une fonction f par la moyenne des valeurs de la fonction évaluées en un ensemble de points x1,…, xN: avec xi, un vecteur de s éléments. La différence entre les méthodes de Monte-Carlo et quasi-Monte-Carlo tient dans le choix des valeurs xi. Alors que la méthode de Monte-Carlo utilise une suite de nombres pseudo-aléatoires, la méthode de quasi-Monte-Carlo utilise la , la suite de Sobol ou la suite de Faure, connue pour leur discrépance faible. L'un des avantages est de permettre une convergence plus rapide de la méthode par l'utilisation de suites à discrépance faible (de l'ordre de O(1⁄N), alors que la méthode de Monte-Carlo est en O(1⁄√N). La méthode de quasi-Monte-Carlo, comme la méthode de Monte-Carlo, trouve son intérêt dans le calcul précis d'intégrales à grand nombre de dimensions, particulièrement demandé en mathématiques financières . (fr) 준몬테카를로 방법(Quasi-Monte Carlo method)은 저불일치 수열(Low-discrepancy sequence)을 사용해 몬테카를로 방법을 개선한 수치적분이다. 준몬테카를로 방법에서는 몬테카를로 방법의 의사난수 대신 등의 저불일치 수열을 사용한다. (ko) Квазі-Монте-Карло метод (з англ. Quasi-Monte Carlo Method) - метод чисельного інтегрування та вирішення деяких інших задач з використанням послідовностей з низьким рівнем невідповідності (так-звані квазі-випадкові послідовності або суб-випадкові послідовності). Це на противагу звичайному методу Монте-Карло, який заснований на послідовності псевдовипадкових чисел. Методи Монте-Карло і квазі-Монте Карло викладені аналогічним чином.Проблема полягає в тому, щоб апроксимувати інтеграл від функції f як середнє значення функції, обчисленої в наборі точок х1, ..., хп: Оскільки ми інтегруємо по х-вимірному одиничному кубі, кожен хi є вектором s елементів. Різниця між методами квазі-Монте-Карло і Монте-Карло - це спосіб вибору хi. Квазі-Монте-Карло використовує послідовності з низьким рівнем невідповідності, такі як послідовності Халтон, Соболеві послідовності, або послідовності Фора (з англ. Faure), в той час як метод Монте-Карло використовує псевдовипадкові послідовності. Перевага використання послідовностей з низьким рівнем невідповідності - швидкість збіжності. Метод квазі-Монте-Карло має оцінку збіжності О(1/n), тоді як у випадку методу Монте-Карло вона становить О(N-0.5). Метод квазі-Монте-Карло останнім часом став популярним в області математичних фінансів і фінансових обчислень. В цих областях багатовимірні числові інтеграли, де значення інтегралу повинне бути оцінене в межах порогового значення ε, трапляються часто. Методи Монте-Карло і квазі-Монте-Карло корисні в таких випадках. (uk) 数值分析中，拟蒙特卡罗方法(Quasi-Monte Carlo method)是使用（一种确定生成的列，也称为拟随机列、次随机列）来进行数值积分和研究其它一些数值问题的方法。而普通的蒙特卡罗方法或蒙地卡罗积分方法使用的是伪随机数。MATLAB中提供了生成如、等超均匀分布列的函数。 拟蒙特卡罗方法和蒙特卡罗方法的具体内容相似，要解决的问题都是通过测量某个可测函数 f 在某些点上的取值，而在数值上求它的积分的近似值。例如要求在单位体积上的积分近似，可以设取的点为x1, ..., xN，那么： 其中的xi都是s维向量。拟蒙特卡罗方法和普通蒙特卡罗方法的区别在于xi的具体选取方式。蒙特卡罗方法用的是伪随机列，而拟蒙特卡罗方法用到的是、等低差异列。使用低差异列的优点是收敛速率较快。拟蒙特卡罗方法可以达到O(1/N)的收敛速率，而普通蒙特卡罗方法的收敛速率则是 O(N-0.5)。 近年来，拟蒙特卡罗方法在金融数学和领域里得到了越来越多的应用，因为其中常常会需要计算高维积分的数值近似。蒙特卡罗方法和拟蒙特卡罗方法可以快捷简单地得到较好的结果。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Pseudorandom_sequence_2D.svg?width=300 |
| dbo:wikiPageExternalLink | http://roth.cs.kuleuven.be/wiki/Main_Page https://web.archive.org/web/20071205010919/http:/www.puc-rio.br/marco.ind/quasi_mc.html http://citeseer.ist.psu.edu/morokoff94quasirandom.html |
| dbo:wikiPageID | 487599 (xsd:integer) |
| dbo:wikiPageLength | 12171 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1118571741 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Monte_Carlo_integration dbr:Monte_Carlo_methods_in_finance dbc:Monte_Carlo_methods dbr:Curse_of_dimensionality dbr:Trapezoidal_rule dbr:Mathematical_finance dbr:Russel_E._Caflisch dbr:Low-discrepancy_sequence dbr:Quasi-Monte_Carlo_methods_in_finance dbr:Low-discrepancy_sequences dbr:Monte_Carlo_method dbr:Pseudorandom dbr:Computational_finance dbr:Computational_physics dbr:Halton_sequence dbr:CiteSeer dbr:Numerical_analysis dbr:Numerical_integration dbr:Discrepancy_theory dbr:Harald_Niederreiter dbr:Newton–Cotes_formulas dbr:Biology_Monte_Carlo_method dbr:Markov_chain_Monte_Carlo dbr:Simpson's_rule dbr:Sobol_sequence dbc:Low-discrepancy_sequences dbr:Randomization |
| dbp:caption | Pseudorandom sequence (en) A Sobol sequence of low-discrepancy quasi-random numbers, showing the first 10 , 100 and 256 points from the sequence. (en) |
| dbp:direction | horizontal (en) |
| dbp:footer | 256 (xsd:integer) |
| dbp:image | Pseudorandom sequence 2D.svg (en) Sobol_sequence_2D.svg (en) |
| dbp:wikiPageUsesTemplate | dbt:ISBN dbt:Multiple_image dbt:Short_description dbt:Use_American_English |
| dct:subject | dbc:Monte_Carlo_methods dbc:Low-discrepancy_sequences |
| rdf:type | yago:WikicatMonteCarloMethods yago:Ability105616246 yago:Abstraction100002137 yago:Cognition100023271 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 |
| rdfs:comment | 준몬테카를로 방법(Quasi-Monte Carlo method)은 저불일치 수열(Low-discrepancy sequence)을 사용해 몬테카를로 방법을 개선한 수치적분이다. 준몬테카를로 방법에서는 몬테카를로 방법의 의사난수 대신 등의 저불일치 수열을 사용한다. (ko) 数值分析中，拟蒙特卡罗方法(Quasi-Monte Carlo method)是使用（一种确定生成的列，也称为拟随机列、次随机列）来进行数值积分和研究其它一些数值问题的方法。而普通的蒙特卡罗方法或蒙地卡罗积分方法使用的是伪随机数。MATLAB中提供了生成如、等超均匀分布列的函数。 拟蒙特卡罗方法和蒙特卡罗方法的具体内容相似，要解决的问题都是通过测量某个可测函数 f 在某些点上的取值，而在数值上求它的积分的近似值。例如要求在单位体积上的积分近似，可以设取的点为x1, ..., xN，那么： 其中的xi都是s维向量。拟蒙特卡罗方法和普通蒙特卡罗方法的区别在于xi的具体选取方式。蒙特卡罗方法用的是伪随机列，而拟蒙特卡罗方法用到的是、等低差异列。使用低差异列的优点是收敛速率较快。拟蒙特卡罗方法可以达到O(1/N)的收敛速率，而普通蒙特卡罗方法的收敛速率则是 O(N-0.5)。 近年来，拟蒙特卡罗方法在金融数学和领域里得到了越来越多的应用，因为其中常常会需要计算高维积分的数值近似。蒙特卡罗方法和拟蒙特卡罗方法可以快捷简单地得到较好的结果。 (zh) En analyse numérique, la méthode de quasi-Monte-Carlo est une méthode d'intégration numérique et la résolution de problèmes numériques par l'utilisation de suites à discrépance faible. Elle s'oppose donc à la méthode de Monte-Carlo qui utilise des suites de nombres pseudo-aléatoires. Les méthodes de Monte-Carlo et quasi-Monte-Carlo se basent sur le même problème : l'approximation de l'intégrale d'une fonction f par la moyenne des valeurs de la fonction évaluées en un ensemble de points x1,…, xN: (fr) In numerical analysis, the quasi-Monte Carlo method is a method for numerical integration and solving some other problems using low-discrepancy sequences (also called quasi-random sequences or sub-random sequences). This is in contrast to the regular Monte Carlo method or Monte Carlo integration, which are based on sequences of pseudorandom numbers. Monte Carlo and quasi-Monte Carlo methods are stated in a similar way.The problem is to approximate the integral of a function f as the average of the function evaluated at a set of points x1, ..., xN: (en) Квазі-Монте-Карло метод (з англ. Quasi-Monte Carlo Method) - метод чисельного інтегрування та вирішення деяких інших задач з використанням послідовностей з низьким рівнем невідповідності (так-звані квазі-випадкові послідовності або суб-випадкові послідовності). Це на противагу звичайному методу Монте-Карло, який заснований на послідовності псевдовипадкових чисел. Методи Монте-Карло і квазі-Монте Карло викладені аналогічним чином.Проблема полягає в тому, щоб апроксимувати інтеграл від функції f як середнє значення функції, обчисленої в наборі точок х1, ..., хп: (uk) |
| rdfs:label | Méthode de quasi-Monte-Carlo (fr) 준몬테카를로 방법 (ko) Quasi-Monte Carlo method (en) Квазі-Монте Карло методи (uk) 拟蒙特卡罗方法 (zh) |
| owl:sameAs | freebase:Quasi-Monte Carlo method yago-res:Quasi-Monte Carlo method wikidata:Quasi-Monte Carlo method dbpedia-fr:Quasi-Monte Carlo method dbpedia-ko:Quasi-Monte Carlo method dbpedia-uk:Quasi-Monte Carlo method dbpedia-zh:Quasi-Monte Carlo method https://global.dbpedia.org/id/4tNdZ |
| prov:wasDerivedFrom | wikipedia-en:Quasi-Monte_Carlo_method?oldid=1118571741&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Pseudorandom_sequence_2D.svg wiki-commons:Special:FilePath/Sobol_sequence_2D.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Quasi-Monte_Carlo_method |
| is dbo:wikiPageDisambiguates of | dbr:QMC |
| is dbo:wikiPageRedirects of | dbr:Quasi-Monte_Carlo_Method |
| is dbo:wikiPageWikiLink of | dbr:Monte_Carlo_integration dbr:Monte_Carlo_methods_for_electron_transport dbr:Bayesian_quadrature dbr:Joseph_F._Traub dbr:Information-based_complexity dbr:List_of_numerical_analysis_topics dbr:Quasi-Monte_Carlo_Method dbr:Russel_E._Caflisch dbr:Low-discrepancy_sequence dbr:Quasi-Monte_Carlo_methods_in_finance dbr:189_(number) dbr:Monte_Carlo_method dbr:Stanisław_Krystyn_Zaremba dbr:Feedback_with_Carry_Shift_Registers dbr:Numerical_analysis dbr:Numerical_integration dbr:Outline_of_finance dbr:Frances_Kuo dbr:Gerhard_Larcher dbr:Harald_Niederreiter dbr:QMC dbr:Randomness dbr:Supersampling dbr:Feynman–Kac_formula dbr:Ian_Sloan_(mathematician) dbr:Markov_chain_Monte_Carlo dbr:Sobol_sequence dbr:Walsh_function dbr:Variance-based_sensitivity_analysis dbr:Martin_Krause_(mathematician) dbr:Multilevel_Monte_Carlo_method |
| is foaf:primaryTopic of | wikipedia-en:Quasi-Monte_Carlo_method |
