Talk:Finite difference

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class High Priority  Field: Analysis


Contents

[edit] Better description needed

The description of finite difference methods seems somewhat muddled - there appears to be a confusion between particular finite difference methods and the general definition of the term. It seems to me that at the very least the article ought to partition itself a little better - for instance, if difference operators are mentioned, it would be nice to at least indicate that there is more than one and that all are derived from Taylor expansions. I don't necessarily feel myself qualified to make any modifications that might be necessary - if anyone is, then perhaps they could edit this topic?

If I could expand on this. "Finite Differences" is about replacing derivatives by differences, it can be applied in 1 dimension or several and to any order of derivative. Perhaps a few examples rather than one would be more informative. "Finite Difference Equation" arises when we substitute finite differences for the derivatives in a differential equation. Closely allied to this is the idea of a method of solution, by putting unknowns in terms of known quantities. In ordinary differential equations this gives a variety of solution methods. In PDEs the methods are called Finite Difference Methods.

[edit] Crank-Nicolson

(Note: Nicholson is a common misspelling of Nicolson. Refer to original paper (1947) or The Mathematics of Diffusion by John Crank.)
Regarding the Crank-Nicolson, I am pretty sure that the convergence order is O(h^2) \, and not O(h^4) \, . The advantage over the implicit method is basically in the improvement of the convergence speed regarding the time step, which is O(k^2) \, instead of O(k) \, of the implicit method.

I decided to post it here so we may discuss it instead of overwriting it, just in case to be sure.

Volemak(talk)

I am copying the discussion from User Talk pages:

Hello. You wrote in finite difference that Crank-Nicolson is fourth-order in space. Could you please make sure that this is true, preferably by giving a reference? I'm pretty certain that Crank-Nicolson is second-order, but it might just be possible that it is fourth-order for this specific setting, and I won't be in my office for some time so it will be hard for me to check it. -- Jitse Niesen (talk) 22:40, 20 December 2005 (UTC)
I will look for a paper source.
But the order can be easily derived.
Lets take the first six members of the Tailor series of f(x − xj) at time t=Nk+1/2
f(x) = a0 + a1x + a2x2 + a3x3 + a4x4 + a5x5 + 0(x6)
we can find the second derivative over x, then find first derivative over time from the heat transfer equation, then find the second derivative over space over df/dt and find the second derivative over time etc.
Thus the Tailor decomposition over x and t will look like:
f(x,t) = a0 + a1x + a2x2 + a3x3 + a4x4 + a5x5 + 0(x6) + D(2a2t + 6a3tx + 12a3tx2 + 20a5tx3 + 0(tx4)) + D2(12a4t2 + 60a5t2x + 0(t2x)) + 0(t3)
where D is the thermal diffusivity.
if we substitute the obtained equation for x=-h,0,+h and t=-k/2 +k/2 into Crank Nicolson scheme, we will see all the terms written are cancelled and the Crank-Nicolson scheme is exact. Thus, the errors came from the terms for x^6 and t^3 and so they are proportional to h^4 and k^2 (we take 2nd order derivative over x and the first over t).


Obviously, to get the fourth order over h we should take care over the boundary conditions. E.g. maintaining the adiabatic b.c as xN − xN − 1 would destroy the 4th order instantly, but the scheme itself is 4th order (if the coefficients are constant).
BTW for the explicit scheme for the special case of r=1/6, we a getting the quadratic error over t and fourth orders over x. I am not sure if we should mention it. abakharev 00:08, 21 December 2005 (UTC)
The easiest way of checking this is to plug the Crank-Nicolson scheme into mathematica, subtract from it the exact derivatives (heat equation that is), and expand all in Taylor series (mathematica has a command for that). One can also do Maple too I think. Symbolic calculations saved my ass a lot of times when dealing with messy finite-difference schemes. Oleg Alexandrov (talk) 16:25, 21 December 2005 (UTC)

[edit] Implicit Method (backward difference)

The recurrence equation in description of the Backward difference is incorrect. Looks like the recurrence relation of forward difference has been restated again.

Backward difference recurrence equation should be Y(x) - Y(x-1)....

I'm afraid I have no idea what you mean. The right-hand side of the recurrence relation for backward differences is at time n+1, and the rhs for forward difference is at time n. There is no Y defined in the article. -- Jitse Niesen (talk) 05:39, 10 April 2006 (UTC)

[edit] Reorganization

I'm proposing a reorganization of this article and finite difference schemes on Talk:Finite difference schemes. Please comment. -- Jitse Niesen (talk) 11:52, 31 July 2006 (UTC)

[edit] Mathematical analysis vs. numerical one

I think there are two different notions of finite difference in math, one is in numerical analysis and another one is in mathematical analysis.

  1. in the first case it is an "mathematical expression of the form f(x + b) − f(x +a)". In second it is an operator which is not a "mathematical expression".
  2. in the first case it is denoted as Δ[f](x) while in the second \Delta_h^m(f,x). I have never saw first notation applied to operator.
  3. the mathematical books can divided in to two groups: first group books mention only forward and backward differencies and say nothing about operators, while second group books work with operators only.
  4. \Delta^{n-1}(\Delta_{}^{}) is usual for operators but almost nonsence for numerical analysis.

It's like operators in fucntional analysis and algebra — much in common but different notions. Mir76 17:46, 16 March 2007 (UTC)

I'm not sure that I understand what you say, but I disagree with there being separate meanings in numerical and mathematical analysis:
1. In my experience, in both fields "finite difference" usually refers to a "mathematical expression of the form f(x + b) − f(x + a)", with the operator being called a "finite difference operator". Can you name some books that use "finite difference" to refer to the operator?
Yes, it is quite common experience of specialist in numerical analysis :) Ok, here goes the first book fell into may hands: Paul L. Butzer, Hubert Berens "Semi-group of operators and approximation", Springer-Verlag, Berlin Heidelberg New York, 1967. Page 257:
Let \Delta^r_hf=[T(h)-I]^rf = \sum\limits_{l=0}^r (-1)^{r-l}\binom{r}{l}f(\cdot+lh) be the right difference of a function f...
I think I have to explain something. Here T(h) is a shift operator (f(x) –> f(x+h)) and I is an identity operator (f(x) –> f(x)). It is the only definition of diffrencies in this book and there are no central differencies in whole book at all.
Next example: Charles K. Chui "An introduction to wavelets", formula (4.1.9), translated back from Russian:
We will use backward differencies defined as (Δf)(x) = f(x) − f(x − 1); (Δnf)(x) = (Δn − 1(Δf))(x).
I'm almost sure I saw something similar in Ingrid Daubechies' "Ten lectures on wavelets" but I cannot find it right now. I can say that Berens and Chui both are very high class mathematicians.
Moreover every book dealing with Besov spaces will use this notation. Mir76 17:55, 18 March 2007 (UTC)
It seems to me that Chui's quote agrees exactly with what I said: The expression f(x) − f(x − 1) is called a "backward difference". The "backward difference operator" is Δ, and the result when you apply this operator is the "backward difference". Similarly, Butzer & Berens say that \Delta^r_hf (the result of applying the operator to a function f) is a "right difference".
Now, it happens quite often that functions and their result is confused in mathematics, so people talk for instance about "the function f(x)" even though it's more precise to say "the function f". So I would argue that possible confusion between the operator and the result of applying the operator does not show that the notion of "finite difference" in mathematical analysis differs from that in numerical analysis. -- Jitse Niesen (talk) 10:56, 19 March 2007 (UTC)


2. The notation L[f](x) is common in numerical analysis and other branches of applied mathematics to refer to the operator L, applied to the function f, and the resulting function evaluated at x; see for instance calculus of variations. The idea is to distinguish operators (which are applied to functions) and functions (which are applied to numbers) by using square brackets [] for the former and round parentheses () for the latter. However, the notation Δ[f](x) is by far not the only one used in numerical analysis. I've also seen (Δf)(x), Δ(f)(x) and Δ(x,x + h)(f). The subscript h is also used frequently in numerical analysis.
I think you are right here but when I have added \Delta_h^n(f,x) to article, Oleg Alexandrov reverted it with some edits of unknown person. That's why I have arranged separate section for analysis. Mir76 17:55, 18 March 2007 (UTC)
3. It's true that some books do not look at the operator aspect. However, there are plenty of numerical analysis books that work with operators. For instance, the equation hD = log(1 + Δ) uses operators, yet I got this equation from a numerical analysis book.
Does that book work with shift operator above? Do all students of numerical analysis understand about operator's notation? I have an experience that answer is No. Mir76 17:55, 18 March 2007 (UTC)
Yes, it uses the shift operator. Regarding your second question, I don't know quite what you mean. I expect that all students will be able to understand the operator notation if it is explained to them. It's not a big deal after all.
You seem to underestimate the amount of mathematical analysis used in numerical analysis. Semi-groups of operators are used in numerical PDEs, approximation theory is a standard part of courses in numerical analysis, and wavelets are arguably as much numerical analysis and mathematical analysis. -- Jitse Niesen (talk) 10:56, 19 March 2007 (UTC)
4. Where do you get the formula Δn − 1(Δ) from? That seems sloppy notation: the domain of Δ is a space of functions so you can't apply Δ to itself.
Surely I can. It is an operator's composition :). See, for example, Chui above. It is really very common definition. That's why I need separate section — to protect this definitions from numerical analysis students. Mir76 17:55, 18 March 2007 (UTC)
Well, normally composition is denoted like \Delta^{n-1} \circ \Delta. In the quote of Chui, he uses Δn − 1(Δf) which is not the same as Δn − 1(Δ).
You are using expressions like log(1 + Δ) above without any problem, but domain of log is (0, \infty), not C[a,b].
Your last sentence is very much against the ethos here: you don't own a section but you have to allow others to edit it. -- Jitse Niesen (talk) 10:56, 19 March 2007 (UTC)
I am quite aware of this. I am happy when my contributions are improved and I am not happy when they are reverted.
5. "It's like operators in fucntional analysis and algebra" — What do you mean with an operator in algebra?
Ok, it was mistranslaton from Russian. I'll try explain it in another words: Consider two operators: first one is multiplication of vector to square matrix, second one is taking a value of function in one fixed point (f(x) —> f(1)). They are both operators. But one of them has eigenvalues whilst other has not. Mir76 16:37, 19 March 2007 (UTC)
6. So, I still think that there are two different notions here. -- Jitse Niesen (talk) 06:45, 18 March 2007 (UTC) I wanted to say: I still don't think that there are two different notions here. Sorry about the confusion. -- Jitse Niesen (talk) 02:46, 19 March 2007 (UTC)
Mir76, there were several issues with your edit. Firstly, you changed the notation for central differences from δ to Δ even though this clashes with the notation for forward differences, but you didn't make this change throughout the whole article. Then you introduce your favorite notation, even though that doesn't seem to add to the article. Finally, you used your notation, instead of the notation used in the rest of the article, to define higher-order differences, writing
\Delta_h^n(f,x) = \Delta_h (\Delta_h^{n-1}(f,x))
where you should have written
\Delta_h^n(f,x) = \Delta_h (\Delta_h^{n-1}(f,x),x).
So there were plenty of reasons to revert and none of them has to do with any difference between mathematical and numerical analysis. -- Jitse Niesen (talk) 10:56, 19 March 2007 (UTC)
Never have did this. I do not know who is 80.7.146.126, he is surely not me. What I have done — added line "Sometimes this difference is denoted \Delta_h(f,\,x)" which is obviously right. After that I used this particular notation for defining higher order differencies since there were no proper definition. And yes, I have made something which looks to you as an two symbols typo — omitted obvious argument. After that, instead of correcting a typo Alexandrov erased my notation and my definition of higher order differences. So I decided that he didn't recognized them (sorry for that assumption) and started another section with operator's point of view. 16:37, 19 March 2007 (UTC)

If there's a difference between the 'mathematical' and 'numerical analytic' uses of the term finite difference, I can't see it. It doesn't matter whether one views it in terms of the f.d. operator or not. JJL 13:01, 19 March 2007 (UTC)

For me main difference is that one thing thing is an expression while other is an operator. Mir76 16:37, 19 March 2007 (UTC)

[edit] Summary

What I had done:

1. Added notation \Delta_h^m(f,x).

2. Added \Delta_h^n = \Delta_h (\Delta_h^{n-1}) (I do not need an argument f(x) here, it is like f(r(t)) = f(r)).

3. Added definition of difference as an operator, not expression (I strongly believe that operator is not expression, e.g. Fourier transform is not an expression).

4. Mentioned some pages where this operator is used.

I need all these four items (and they are not my fantasies, as you can see). I do not know how to incorporate this issues (especially #3) into existing article without breaking it. It is too much biased for numerical analysis now. So I started another section which is mathematical analysis oriented. I will be really happy if somebody will merge (not simply revert) this two sections in one. Or we can separate them to different articles. Mir76 16:37, 19 March 2007 (UTC)

Nobody reverted your sections additions, here's the diff. I just removed the intro, which was incorrect, and renamed a section. All the other text you put in including the formulas did not change. So I had basically done the merge you are suggesting above. Oleg Alexandrov (talk) 03:02, 20 March 2007 (UTC)
Ok, I have to acknowledge — at that time I haven't read the diff carefully, I only saw several added by me paragraphes were removed all together. I didn't like them, but they were needed to explain splitting of the article. Let state that we both have reverted each other once (March, 12 and March, 16).
But this doesn't help much, since after your second edit article became really weird (see http://en.wikipedia.org/w/index.php?title=Finite_difference&oldid=115574544). There were two definitions of difference, two definitons of higher orders differences, two subsections concerning derivatives and no explanation why article is splitted in such way. And, more curious, finite difference is surely an operator, but finite difference operator is another thing, not equal to finite difference. So your new section title wasn't very good.
I can not say it was merging. Mir76 08:57, 20 March 2007 (UTC)
It was not at all a revert, and it did not have the "revert" word in the summary. Where did you get that from? I just removed the incorrect intro. Oleg Alexandrov (talk) 14:55, 20 March 2007 (UTC)
In numerical analysis we use the operator notation to develop new finite difference formulas. A finite difference f(x+h)-f(x) is the result of applying a finite difference operator to a function. You'll find this throughout books on the num. sol. of PDEs, for example. To me, it's like distinguishing between saying that the derivative of x^2 is an operator that acts on x^2 to produce another function and saying that the derivative of x^2 is 2x, the result of having applied that operator. I use "derivative" for both of these closely related ideas. If you're trying to distinguish here between a finite difference operator and the result of that operation from the point-of-view that you could ask questions of the operator like "Is it linear and bounded, and what is its spectrum?" then it's true that those are different perspectives on it. But I don't see two corresponding entries for theoretical vs. applied derivative, integral, etc. So, I think that this isn't a distinction worth drawing here, and I definitely feel that num. analysts view it as an operator too...a very useful one! I'm inclined to revert. JJL 17:52, 19 March 2007 (UTC)
"I'm inclined to revert" means erasing items 1-4 above? Mir76 08:57, 20 March 2007 (UTC)
Or at least integrating them into the article. I still don't believe there's a distinction here that's important at the level of this entry. There are lots of things that can be viewed as operators. Yes, del and del(f) are not the same object, but they're the same idea and don't arise from/reside in wholly separate areas of math. I think they're two closely related aspects of one thing and not two different things. Where else is a sepcific operator given its own page/subpage, separate from what it does? JJL 12:41, 20 March 2007 (UTC)
In my part of article operator is defined and clearly explained what does he do - he returns another function. In first part difference returns a number and it is also explicitly stated. Mir76 16:50, 21 March 2007 (UTC)
May be the main reason for me to create separate section was that I personally do not like definition
A finite difference is a mathematical expression of the form f(x+b) − f(x+a)
since it is only half of the truth. I do not know how to insert operators there. I cannot see that derivative or integral are defined as an expression. Mir76 08:57, 20 March 2007 (UTC)

I give up. I can not seamlessly integrate those items into numerical analysis part of article since I am not a specialist in that field and can do more damage than profit. I have tried already without much success. May be you can do it better. I have tried to made the intro softer I ask not to remove it before real merge will be done. Mir76 16:50, 21 March 2007 (UTC)

[edit] Explain 'Generaliztions' notation?

Right now I'm stealing Finite Differences for a problem, thanks to the contributors of this article. I found the article useful, helpful, understandable, and the discussion also interesting and helpful. I was especial gratified (proud) to see the quality and level of collaboration shown here in discussion. Well done. I think this collaboration illustrates that the voice and views of non-experts are an important aid to communication by experts. :)

I found a difficulty in the article, however, and hope it can be clarified. In viewing the article I found the notation in 'Generalizations' confusing where it said :\Delta_h^\mu[f](x) = \sum_{k=0}^N \mu_k f(x+kh),. The rest of the article refers to the superscript on Delta as the 'order', and it would therefore appear the mu on Delta should be N here. [also n is used throughout instead of N, so perhaps n might be regarded as more consistent?] Thank You. —Preceding unsigned comment added by 76.191.132.120 (talk) 23:04, 23 January 2008 (UTC)

Order of differantional operator depends on order of polynomial it annihilates. Classical finite differences of order n kills polinomials of order n-1. If you change the coefficients to μk it can kill or can kill not polynomials of particular degree — this depends upon μk. Here N is a length of coefficients vector μk.
So notion of order is not applicable here and free superscript place was used for another (but having similar meaning) parameter. This should be incorporated into main article sometime... Mir76 (talk) 09:55, 12 March 2008 (UTC)