The content ofMethods of successive approximation wasmerged intoIterative method on 12 September 2024. The former page'shistory now serves toprovide attribution for that content in the latter page, and it must not be deleted as long as the latter page exists. For the discussion at that location, see itstalk page.

This article is ratedB-class on Wikipedia'scontent assessment scale. It is of interest to the followingWikiProjects:

MathematicsLow‑priority This article is within the scope ofWikiProject Mathematics, a collaborative effort to improve the coverage ofmathematics on Wikipedia. If you would like to participate, please visit the project page, where you can jointhe discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated asLow-priority on theproject's priority scale.

First, it ignores work by Gauss predecessors, including Newton. Second, it ignores the real world drivers (astronomy, business, and military issues) behind the effort to establish quicker tabulation methods. --70.112.146.19617:30, 8 July 2006 (UTC)[reply]

I stumbled upon this article and was surprisedNewton's method was not even mentioned indeed. Isn't it a good simple example of iterative method?--Grondilu (talk)16:32, 8 March 2014 (UTC)[reply]

In iterative methods, there may be cases where the cost of moving from one point to the next varies with location (e.g., it might cost more to move from (1,0,0,0) to (4,3,2,1) than to (2,0,0,0)); there also may be cases where the cost of evaluation is location-dependent (e.g., evaluatingf(1000,1000) may cost less than evaluatingf(42,37)). In such cases, the optimal "next guess" would be different than if these constraints did not exist. Is there literature on this sort of thing?—Ben FrantzDale04:53, 27 April 2007 (UTC)[reply]

Can you give an example of a realistic problem where evaluating a cost function at a point requires significantly more computation than evaluating the same cost function at a different point?Oleg Alexandrov (talk)06:22, 27 April 2007 (UTC)[reply]

One thing I'm thinking about is mesh adaptation for finite element analysis. Refining the mesh lets you explore a higher-dimensional solution space but at a computational cost. Another example is minimizing the energy of a bunch of atoms. Moving a bunch of atoms isO(N). Suppose you are doing steepest decent. If you knew that the force was almost zero for most atoms and only significant forn atoms, you could move from one configuration to another inO(n) time, putting off theO(N) step until it becomes necessary. I have other crazy ideas in mind as well.

A less-abstract example came up in real life. I was hiking with my brother in the hills near San Diego (photo). We were trying to get to the top of a hill. There was no trail, so we were bushwhacking. From a distance, it wasn't possible to tell if bushes were small and could be walked over or were head-height and tangled. We tried to get to the top as quickly as possible, so we went for the shortest route, but as we went along, the bushes slowed us down, so we followed the path that seemed locally to be optimal in terms of time and in terms of scratches from branches. If we had knowna priori that basically the top of the hill was densely covered in one convex patch, we could have used that knowledge to first find the edge of the dense vegetation, then traverse that edge to find the highest easily-walkable point, then go from there to the top.

Does that make sense? Are there mathematical tools to discuss such things?—Ben FrantzDale07:34, 27 April 2007 (UTC)[reply]

Interesting question,Ben FrantzDale.

The algorithms used inmotion planning andpathfinding are more relevant to physically climbing a physical hill than mathematicalhill climbing methods that metaphorically climb an imaginary, abstract hill.

Many people are trying to collect enough shortcut heuristics, some of them similar to the one you mentioned, such that applying all of them helps solve theprotein folding problem to give results that are "accurate enough" to be useful in a reasonable amount of CPU time.

Similarly,n-body simulation#Calculation optimizations there are shortcut heuristics that give "accurate enough" simulations in less CPU time; and a few characteristics that can be calculated directly without doing any simulation.

Is there a general field of study that covers all of these very specific examples? --DavidCary (talk)15:13, 27 March 2015 (UTC)[reply]

Standard division algorithms – restoring and non-restoring procedures - iterative produce one digit of the final quotient per iteration. The division methods are all based on the form X = b / A, where•X = Quotient•b = Dividend•A = DivisorDivision methods are all based on a standard recurrence equation:

       Wk+1 =2Wk  - Aqk,

where:•Wk = the partial remainder of the division,•qk = the digit of the quotient X in k-th position, •A = the divisor.

Both restoring and non-restoring divisions are based on the analysis of the sign of the partial remainder Wk. If Wk >= 0, then the divisor A is subtracted from the partial remainder Wk , if Wk < 0 then the divisor A is added to the partial remainder Wk . Both methodes doesn’t take into account the value of the partial remainder Wk , only its sign.

Taking into account the value of the most significant digit of the partial remainder Wk , can accelerate the division process. If the most significant digit of the Wk is “1”, then we choose according to the sign of Wk - addition or subtraction the divisor A to the Wk and write -1 or +1 to the correspondingly position of the quotient X as in non-restoring division procedure.

But if the most significant digit of the Wk is “0”, then we skip this iteration and write “0” to the correspondingly position of the quotient X . So we get the quotient in the ternary system with the set of digits: {+1, 0, -1}, which is converted then very easy into traditional binary system.

Evidently this approach can be generalized to the vectors and matrices. For example if A - m-th order matrix, b – the right part of the linear system of equations, X – the vector of the unknowns, we have:X = b A-1 ,or:AX - b = 0For the k-th iteration:AXk - b = Wk,where:

    Wk   - value of residual vector for k-th iteration;       Xk   - value of result vector of unknowns on k-th iteration.

vladimir@baykov.de— Precedingunsigned comment added byVladimir Baykov (talk •contribs)14:52, 12 March 2011 (UTC)[reply]

As pernumerical analysis, "iterative methods form successive approximations that converge to the exact solution".fgnievinski (talk) 02:56, 21 December 2023 (UTC)fgnievinski (talk)02:56, 21 December 2023 (UTC)[reply]

  YMerge completedKlbrain (talk)18:51, 12 September 2024 (UTC)[reply]

It is interesting that someone deleted the articles on IDRstab and the mentioning of IDR, which is the fastest Krylov method for non-symmetric systems. Makes no sense, especially since that is the first go-to method for everyone knowledgeable enough, which this article ironically prevents.31.17.92.45 (talk)17:34, 25 November 2024 (UTC)[reply]

• B-Class mathematics articles
• Low-priority mathematics articles

• Wikipedia pages using copied template
• Wikipedia pages using merged-from template without oldid