View source for Testwiki:Property proposal/convergence rate

=== {{TranslateThis | anchor = en
| en = order of convergence (changed from "convergence rate")
<!-- |xx = property names in some other languages -->
}} ===
{{Property proposal
|status			= withdrawn 
|description		= {{TranslateThis | en = the rate at which a sequence or numerical method converges
<!-- | xx = descriptions in other languages -->
 }}
|subject item           = {{Q|1783502}} <!-- item corresponding to the concept represented by the property, if applicable; example: item child (Q7569) for property child (P40) -->
|infobox parameter	= <!-- Wikipedia infobox parameters, if any; ex: "population" in [[:en:template:infobox settlement]] -->
|datatype		= item <!-- put datatype here (one of: item, external-id, string, media, coordinates, monolingual text, multilingual text, time, URL, number, geo-shape, tabular, lexeme, form, sense, mathematical expression, or a possibly new one) -->
|domain			= {{Q|24262840}} {{Q|133250}} <!-- entity type (item, property, lexeme, form, sense) and types of items that may bear this property; give QIDs if possible -->
|allowed values		= instancesof {{Q|269878}} <!-- type of linked items (Q template or text), string pattern (regex if possible), list or range of allowed values, etc. -->
|allowed units          = <!-- units that are allowed for values of this property -->
|source			= <!-- external reference URL, Wikipedia list article, etc. -->
<!-- you should provide 3 examples at least-->
|example 1		= {{Q|868454}} → <math> O(h^2) </math> {{P|642}} {{Q|97796690}} {{P|2210}} <step size>
|example 2		= {{Q|2877013}} → quadratic? to-do: look up convergence rate of BFGS
|example 3		= {{Q|1199743}} → <sublinear> <with respect to> <iteration count> <when applied to> <convex function> [http://www.stat.cmu.edu/~ryantibs/convexopt-F13/scribes/lec6.pdf]
|example 4		= {{Q|1199743}} → <linear> <with respect to> <iteration count> <when applied to> <strictly convex function> [http://www.stat.cmu.edu/~ryantibs/convexopt-F13/scribes/lec6.pdf]
|example 5              = {{Q|17086396}} → <quadraticall> <when applied to> <convex function> [https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization#Convergence]
|planned use            = <!-- what use do you plan to make of the property within the next month -->
|number of ids          = <!-- for identifiers, the number of ids available from the source -->
|expected completeness  = <!-- for identifiers, the coverage we can hope for in Wikidata: Q21873886 (always incomplete) or Q21873974 (eventually complete) -->
|formatter URL		= <!-- for identifiers, URL pattern where $1 replaces the value -->
|external links         = <!-- for identifiers, search string to pass to sister projects' Special:LinkSearch pages, e.g. example.com  -->
|see also               = {{P|3755}}, {{P|3757}}, {{P|3756}}, {{P|3752}}, {{P|3754}} {{P|3753}}, {{Q|269878}}
|filter			= <!-- sample: 7 digit number can be validated with edit filter [[Special:AbuseFilter/17]] -->
|robot and gadget jobs	= <!-- Should or are bots or gadgets doing any task with this? (Checking other properties for consistency, collecting data, etc.) -->
|subpage		= convergence rate
|topic			= natural science
}}

====Motivation====
Well-posed numerical methods (theoretically) converge to the exact solution as <math>n \to a</math>. For discretized methods, <math>n</math> is the grid size of the discretization and <math>n \to \infty</math>. For iterative methods, <math>n</math> could be the number of iterations and <math>n \to \infty</math>. Alternatively, for iterative numerical methods for solving differential equations, <math>n</math> is the tiem-step size and <math>n \to 0</math>. In each case, there is an upper bound on the on the error of the method as a function of <math>n</math> as <math>n \to a</math>. It would be useful to have methods categorized according to this property. 

Specifically, I am proposing that we add a property whose subject is the big-O order of convergence for the method. That is, we would set <order of convergence> <g(n)> where g(n) is a function such 
<math> f(x)=O(g(x)) \text { as } x \rightarrow a </math> 
if <math> \limsup _{x \rightarrow a}\left|\frac{f(x)}{g(x)}\right|<\infty </math>

There are a lot of definitions that are used similarly, so I'm going to list them here and we'll try to sort them out.
* Rate of convergence: if a sequence converges linearly,  <math>\mu := \lim _{k \rightarrow \infty} \frac{\left|x_{k+1}-L\right|}{\left|x_{k}-L\right|}</math> is called the ''rate of convergence''
* If a sequence converges to a limit, then r

The following excerpt from [http://fourier.eng.hmc.edu/e176/lectures/NM/node3.html] provides clear definitions of order and rate of convergences.
::"whether this iteration will converge, and, if so, the rate of convergence. Specifically we use the following to represent how quickly the error \(e_{n}=x_{n}-x^{*}\) converges to zero: <math> \lim _{n \rightarrow \infty} \frac{\left|e_{n+1}\right|}{\left|e_{n}\right|^{p}}=\lim _{n \rightarrow \infty} \frac{\left|x_{n+1}-x^{*}\right|}{\left|x_{n}-x^{*}\right|^{p}}=\mu</math> Here \(p \geq 1\) is called the order of convergence, the constant \(\mu\) is the rate of comergence or asymptotic error constant."
I think it makes sense to create an order of convergence (OC) property, but not a rate of convergence (RC). The reason for this, is that OC is (1) a much more important property of an algorithm and (2) there will only be (in practice) a limited number of values. We'll have logarithmically, sublinear, linear, quadratic, cubic, quartic, and maybe a few more. Whereas RC could be any real number. 

[[User:The-erinaceous-one|The-erinaceous-one]] ([[User talk:The-erinaceous-one|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 07:47, 31 July 2020 (UTC)


===={{int:Talk}}====