text:
# Overview

Delny ===== This package contains some Python modules for Delaunay triangulation using the Qhull C library libqhull. Prerequisites ============= Before the installation you will need an installation of qhull 2003.1 including it's header files and libqhull in the standard locations for your system. The _qhull module is an extension module and needs this to compile. Next the numpy module for Python should be available, also including it's development files in the standard locations. Note that setup.py import numpy to find the relevant C include directories, so even to run setup.py you will need numpy to be available. And of course a proper Python installation with the header files and other development files. For Debian and Ubuntu these are the packages you want, some may depend on each other: python python-dev python-numpy libqhull5 libqhull-dev Installation ============ Delny uses the Distutils, so to install run $./setup install from within Delny's root directory. Or to install in your home directory for example, make sure ~/lib/pyton exists and is included in your Python path (by setting the PYTHONPATH environment variable for instance) and run:$ ./setup install --home=~ For more information on the installation (recommended!) using Distutils use: $./setup --help Extensive online Distutils documentation for sysadmins can be found on http://www.python.org/inst/inst.html Testing the installation ======================== Tests are included under the subdirectory test'. Files testing an individual module name "module" will be called "test_module", to test all modules at once there is a convenience script all.py'. If you want to run them make sure the correct delaunay' package will get imported (see NOTE under "Using Delny" below), so to test a recent build e.g.:$ ./setup build $cd build/lib.linux-i686-2.3 # or whichever dir for your setup$ ../../test/all.py If tests fail be sure to check the BUGS' file to see if there is any information about them. Using Delny =========== Once installed, information on how to use is available from within Python as: import delaunay help(delaunay) NOTE: when the current directory is the package root the Python interpreter will import the Delaunay package form there instead as from the installed location because it comes first in sys.path. This results in an error as __init__.py tries to load the _qhull module which is not available there as it is provided by _qhull.so which is only in the build/ directory and in it's installed directory. Make sure you are using the package with the compiled extension module. Changes in 0.4.1 ================ * Fix numpy transition, the python code was still using numeric. * Get the numpy installation directory from numpy, instead of assuming it will be in a system-default location. * Use the Qz option so the 2D square works, remove the extra vertex from the output so it's transparent to the user. Upgrading to 0.4.0 ================== The only change is to use the numpy package instead of numeric. No other changes where made. Upgrading from pre 0.2.0 ======================== No incompatible API changes where made. Only the delaunay.facets_indices() method has been added. Most changes where internally inside the _qhull module which is now much cleaner and more flexible. Note that there is still no guaranteed API stability as long as 1.0 is not reached. In fact changes are still planned. The new versioning sheme doesn't use the a' or b' suffixes anymore for alpha or beta. Just know that there's no stability untill 1.0 is reached. The alpha and beta releases may come back when 1.0 is reached or just before. Upgrading from pre 0.1.0a2 ========================== Please note the API changes, this is still alpha so you should have know this would happen. Basically: (i) the package name is changed to "delaunay" (formerly "Delaunay"). (ii) the format for method (and function) names has changed. Wat formally was "get_this_stuff()" is now "getThisStuff()". (iii) the tests have moved to the directory which they are testing, that is "Delny-xxx/tests/*" has moved to "Delny-xxx/delaunay/tests/*" As always, hopefully these things won't change anymore... Using qhull3.1 ============== When using qhull3.1 it will be necessary to modify the delaunay/_qhullmodule.c file. Near the top you will see a line where #define QHULL_31_COMP=1 is commented out, uncomment this and it should work for qhull3.1. A more automated way for this is envisioned for a future release. Please note that any earlier version of qhull does not support triangulated output (Qt) and thus will not normally work with Delny, qhull3.1 is the oldest version you can use. Feedback ======== Please send feedback and bug reports to floris.bruynooghe@gmail.com. Authors ======= This package was written by Floris Bruynooghe (floris.bruynooghe@gmail.com). Ola Skavhaug <skavhaug@simula.no> contributed the initial patch for referring to nodes by index.


text:
# Is the limit of a sequence of characteristic functions of probability measures a characteristic function of a measure?

Given a sequence of probability measure $$P_n$$ on $$\mathbb R$$ with the Boreal sigma algebra, define $$f_n = \int e^{ixt}dp_n$$, and suppose that $$f_n \to f$$ for some $$f$$ bounded measurable, is it true that there exists some $$p$$ such that $$f = \int e^{ixt}dp$$?

My intuition tells me that this is false, but I cannot come up with an example. The example that I tried: Let $$p_n$$ be the Gaussian with mean $$0$$, variance $$\frac{1}{n^2}$$, then the characteristic function converges to the constant $$1$$. However, $$1$$ is the characteristic function of some dirac delta function.

Instead of having Gaussian with decreasing variance, let $$p_n$$ be Gaussian with mean 0 and variance $$n$$. This gives the counterexample you are looking for. In general the continuity theorem states that if the limiting function $$f$$ is continuous, then there exists such a $$p$$, but not otherwise.

format: plain


text:
# Series Derivative

## Prompt

“Write the first 5 terms of y”(x).”

where y”(x) is the second derivative of y(x) expanded as a series solution.

## Context

This SWBQ helps students to see what happens to a power series when derivatives are taken as a lead-in to reindexing a sum.

## Wrap Up

After the terms have been written, discuss how the terms can be reindexed so that the sum has the same powers of xn as other sums in the differential equation.

##### Views

New Users

Curriculum

Pedagogy

Institutional Change

Publications


text:
TL;DR

On with TASK #2 from The Weekly Challenge #161. Enjoy!

# The challenge

A pangram is a sentence or phrase that uses every letter in the English alphabet at least once. For example, perhaps the most well known pangram is:

the quick brown fox jumps over the lazy dog

Using the provided dictionary, so that you don’t need to include individual copy, generate at least one pangram.

Your pangram does not have to be a syntactically valid English sentence (doing so would require far more work, and a dictionary of nouns, verbs, adjectives, adverbs, and conjunctions). Also note that repeated letters, and even repeated words, are permitted.

BONUS: Constrain or optimize for something interesting (completely up to you) […]

# The questions

Only a few annoying one:

• is it OK to consider uppercase and lowercase as the same letter? I’ll assume yes because of the constraint on the provided dictionary
• are you mean to give such an open space for coming up with something interesting?!?

# The solution

OK, I like randomness because it gives the perfect excuse for not doing things properly! This time, just to exercise this bit of laziness a bit, we’ll try to build something that might seem like it makes some sense.

We’ll be using a Markov Chain text generator: something that, based on how frequently words appear after other words, tries to generate a text based on the same statistics.

As the base of our generator we’ll be taking the book Three men in a boat (to say nothing of the dog), because it’s funny and I was recently reminded about it. Just to take advantage of the latest and greatest typo fixes, we’ll be downloading it dynamically from the internet:

#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';

use HTTP::Tiny;
use constant DEFAULT_BOOK_URL =>
'https://www.gutenberg.org/cache/epub/308/pg308.txt';
use FindBin '$Bin'; use List::Util 'sum'; # Assume Unixish filesystem my$dictionary_file = shift // "$Bin/../../../data/dictionary.txt"; my$book_url = shift // DEFAULT_BOOK_URL;

my $dictionary = read_dictionary($dictionary_file);
my $book = get_stuff($book_url);
my $model = markov_model($book, $dictionary); my ($src, $word, %hits, @trail); while (keys(%hits) < 26) {$src = $model->{$word // ''} // $dictionary; push @trail,$word = random_word_draw($src); ++$hits{$_} for split m{}mxs,$word;
}

say join ' ', @trail;

sub random_word_draw ($weighted_candidates) { my$total = sum values $weighted_candidates->%*; my$draw = rand $total; # definitely space for improvement... for my$word (keys $weighted_candidates->%*) {$draw -= $weighted_candidates->{$word};
return $word if$draw < 0;
}
die "unreached, hopefully\n";
}

sub read_dictionary ($filename) { open my$fh, '<:encoding(utf-8)', $filename or die "open():$!\n";
return { map {chomp; $_ => 1} readline$fh };
}

sub get_stuff ($url) { my$response = HTTP::Tiny->new->get($url); die "$response->{status} $response->{reason}\n" unless$response->{success};
return $response->{content}; } sub markov_model ($text, $dictionary) { my$previous = undef;
my %successors_for;
for my $word (split m{[^a-z]+}mxs, lc$text) {
if ($dictionary->{$word}) {
$successors_for{$previous}{$word}++ if defined$previous;
$previous =$word;
}
else {
$previous = undef; # restart } } return \%successors_for; }  Now, isn’t this a beautiful concoction of overengineering, derailing and not giving a dime about how and in how many ways this can be improved? As an example, the restart might just be avoided, by only counting letters from allowed words while also using words outside the dictionary. Anyway, here’s a run: grinds subtraction belfries arduously agitating putties inelegant consults loftiest mollify concussions municipalities rascals rattler cheeped textile whimpered medleys transfers rewarding empties enormous prices for about its best to take your life was sure it there rode missing his board by the project freshman superseding dressers berets capitalist forage arterial reconciling tandem scooters lazier rabbles abridge seclude overstep madams jell grub eluding sneakiest certain number of five we were into it again an evening the grave as a flesh and live shameful conduct of his hair round before the woods all but it is certainly rather be worrying work is to put upon the sail at this seemed that dipped down at the man hobbling across your time either bank of justice to sell your fellow in its would break off in the wall and he rose growling at all the boat and tried to a knock kneed broken and at the boat they know after a bit of the evening however is most virulent form the husband she could not care or not lie in my friends watch me this agreement will he finished we went on its king the lock it up the water and he said it about donations to ever tried to have been a rock which he swore he wanted more would all the current they said seven and putting my wrist and sit and king the bottom of god draws nearer and with which are not know that is doing more and sat on the bank from this work and nothing whatever way back with me half dressed nothing about take your guessing it is always a fearful row them and then that it down with one evening we had she does you saw on rocks and have her own bedroom of the wave comes without betraying any you took up from the people gather together so sad and look and a few he would not agree to a fraternity in life that wash up his mother gently down not like doing a very big dogs is and the pie between them it you must appear to wake you will do it made our school master had been very happy to be altered foresee worsens aisles horizons grislier vogue quips We’ll translate this into Raku, too, with just a slight concession to my ubiquitous laziness in that I don’t really want to search the equivalent of using FindBin at this point. Apart from this, it does everything the other program does: #!/usr/bin/env raku use v6; use HTTP::Tiny; constant \DEFAULT_BOOK_URL = 'https://www.gutenberg.org/cache/epub/308/pg308.txt'; sub MAIN (Str:D$dictionary-file, Str:D $book-url = DEFAULT_BOOK_URL) { my$dictionary = read-dictionary($dictionary-file); my$book = get-stuff($book-url); my$model = markov-model($book,$dictionary);

my ($src,$word, %hits);
my @trail = gather while %hits.elems < 26 {
$src =$model{$word // ''} //$dictionary;
take $word = random-word-draw($src);
++%hits{$_} for$word.comb;
};
@trail.join(' ').put;
}

sub random-word-draw ($weighted-candidates) { my$total = $weighted-candidates.values.sum; my$draw = $total.rand; for$weighted-candidates.kv -> $word,$weight {
$draw -=$weight;
return $word if$draw < 0;
}
die "unreached, hopefully\n";
}

sub read-dictionary ($filename) {$filename.IO.words.map({$_ => 1}).Hash; } sub get-stuff ($url) {
my $response = HTTP::Tiny.new.get($url);
die "$response<status>$response<reason>\n"
unless $response<success>; return$response<content>.decode;
}

sub markov-model ($text,$dictionary) {
my $previous = Nil; my$successors-for;
for $text.lc.split(/<-[ a..z ]>/) ->$word {
if $dictionary{$word}:exists {
$successors-for{$previous}{$word}++ if defined$previous;
$previous =$word;
}
else {
$previous = Nil; # restart } } return$successors-for;
}

And now – would you guess? Stay safe!!!


text:
## General discussion

### Is there an open source SIS?

{$a->নাম} - {$a->তারিখ} দ্বারা
Number of replies: 1

SIS are very expensive. Is there an open alternative out there? If so, has anyone used it and what are the things a school would need to know before taking the leap?


text:
Browse Questions

# Show that $y = \log (1+x)-\large\frac{2x}{2+x}$ is an increasing function of x for all value of x > -1.

Can you answer this question?


text:
# IBDP Physics 3.1 – Thermal concepts: IB Style Question Bank SL Paper 2

### Question

A sample of vegetable oil, initially in the liquid state, is placed in a freezer that transfers thermal energy from the sample at a constant rate. The graph shows how temperature T of the sample varies with time t.

The following data are available.
Mass of the sample = 0.32 kg
Specific latent heat of fusion of the oil = 130 kJ kg–1
Rate of thermal energy transfer = 15 W

a. Calculate the thermal energy transferred from the sample during the first  30 minutes. [1]

b. Estimate the specific heat capacity of the oil in its liquid phase. State an appropriate unit for your answer.[2]

c. The sample begins to freeze during the thermal energy transfer. Explain, in terms of the molecular model of matter, why the temperature of the sample remains constant during freezing. [3]

d. Calculate the mass of the oil that remains unfrozen after 60 minutes.[2]

### Ans:

a. «15x30x60» = 27000 «J»

b. 27 x 10 3 = 0.32 x c x (290  250) OR 2100 J kg -1 K -1 OR J kg -1 0 C -1

c.

«intermolecular» bonds are formed during freezing ✓
bond-forming process releases energy
OR
«intermolecular» PE decreases «and the difference is transferred as heat» ✓
«average random» KE of the molecules does not decrease/change ✓
temperature is related to «average» KE of the molecules «hence unchanged» ✓

d.

mass of frozen oil   27x 10 3/130 x 10 3 = 0.21 kg
unfrozen mass «= 0.32 −0.21» = 0.11«kg» ✓

### Question

This question is about thermal properties of matter.

a

Explain, in terms of the energy of its molecules, why the temperature of a pure substance does not change during melting.[3]

b.

Three ice cubes at a temperature of 0°C are dropped into a container of water at a temperature of 22°C. The mass of each ice cube is 25 g and the mass of the water is 330 g. The ice melts, so that the temperature of the water decreases. The thermal capacity of the container is negligible.

The following data are available.

Specific latent heat of fusion of ice $$=$$ 3.3 $$\times$$ 105J kg–1

Specific heat capacity of water $$=$$ 4.2 $$\times$$ 103 J kg–1 K–1

Calculate the final temperature of the water when all of the ice has melted. Assume that no thermal energy is exchanged between the water and the surroundings.[4]

### Markscheme

a

energy supplied/bonds broken/heat absorbed;

increases potential energy;

no change in kinetic energy (so no change in temperature);

b.
use of M $$\times$$ 4.2 $$\times$$ 103 $$\times$$ ∆θ
ml $$=$$ 75 $$\times$$ 10–3 $$\times$$ 3.3 $$\times$$ 105 / 24750 J;
recognition that melted ice warms and water cools to common final temperature;
3.4ºC;

### Question

This question is about internal energy.

(i) Mathilde raises the temperature of water in an electric kettle to boiling point. Once the water is boiling steadily, she measures the change in the mass of the kettle and its contents over a period of time.

The following data are available.

Initial mass of kettle and water = 1.880 kg
Final mass of kettle and water = 1.580 kg
Time between mass measurements = 300 s
Power dissipation in the kettle = 2.5 kW

Determine the specific latent heat of vaporization of water.

(ii) Outline why your answer to (b)(i) is an overestimate of the specific latent heat of vaporization of water.

## Markscheme

(i) mass lost in 300 s=(1.880-1.580)=0.3 (kg);
(energy supplied=750 kJ) (do not award credit for this line)
L=2.5 MJ kg–1(unit must appear correctly here)
Award [2] for a bald correct answer.

(ii) energy will be transferred to surroundings; } (accept energy is lost by/from kettle to surroundings)
so calculated energy to water is too large / change in mass too large;
(hence overestimate)
Award [0] for a bald correct answer.
Treat references to energy gained by kettle as neutral; the kettle is at a constant temperature.

### Question

This question is about thermal energy transfer.

A hot piece of iron is placed into a container of cold water. After a time the iron and water reach thermal equilibrium. The heat capacity of the container is negligible.

a

Define specific heat capacity.[2]

b.

The following data are available.

Mass of water = 0.35 kg
Mass of iron = 0.58 kg
Specific heat capacity of water = 4200 J kg–1K–1
Initial temperature of water = 20°C
Final temperature of water = 44°C
Initial temperature of iron = 180°C

(i) Determine the specific heat capacity of iron.

(ii) Explain why the value calculated in (b)(i) is likely to be different from the accepted value.[5]

## Markscheme

a

the energy required to change the temperature (of a substance) by 1K/°C/unit degree;
of mass 1 kg / per unit mass;

b.

(i) use of mcΔT;
0.58×c×[180-44]=0.35×4200×[44-20];
c=447Jkg-1K-1≈450Jkg-1K-1;

(ii) energy would be given off to surroundings/environment / energy would be absorbed by container / energy would be given off through vaporization of water;
hence final temperature would be less;
hence measured value of (specific) heat capacity (of iron) would be higher;

### Question

Part 2 Internal energy

Humans generate internal energy when moving, while their core temperature remains approximately constant.

a

Distinguish between the concepts of internal energy and temperature.[3]

b.

An athlete loses 1.8 kg of water from her body through sweating during a training session that lasts one hour.

Estimate the rate of energy loss by the athlete due to sweating. The specific latent heat of evaporation of water is 2.3×106 J kg–1.[2]

## Markscheme

a

internal energy:
total energy of component particles (in the human);
comprises potential energy + (random) kinetic energy;

temperature:
measure of average kinetic energy of particles;
indicates direction of (natural) flow of thermal energy;
internal energy measured in J and temperature measured
in K/°C ; (both needed)
(accept alternative suitable units)

b.

total energy lost=2.3×106×1.8(=4.14×106J);
1.2 kW;

Question

Part 2 Melting of the Pobeda ice island

a

The Pobeda ice island forms regularly when icebergs run aground near the Antarctic ice shelf. The “island”, which consists of a slab of pure ice, breaks apart and melts over a period of decades. The following data are available.

Typical dimensions of surface of island = 70 km × 35 km
Typical height of island = 240 m
Average temperature of the island = –35°C
Density of sea ice = 920 kg m–3
Specific latent heat of fusion of ice = 3.3×105J kg–1
Specific heat capacity of ice = 2.1×10$$^3$$J kg–1K–1

(i) Distinguish, with reference to molecular motion and energy, between solid ice and liquid water.

(ii) Show that the energy required to melt the island to form water at 0°C is about 2×1020J. Assume that the top and bottom surfaces of the island are flat and that it has vertical sides.

(iii) The Sun supplies thermal energy at an average rate of 450 W m–2 to the surface of the island. The albedo of melting ice is 0.80. Determine an estimate of the time taken to melt the island assuming that the melted water is removed immediately and that no heat is lost to the surroundings.[8]

b.

Suggest the likely effect on the average albedo of the region in which the island was floating as a result of the melting of the Pobeda ice island.

[2]

### Markscheme

a

(i) in water, molecules are able to move relative to other molecules, less movement possible in ice / in water, vibration and translation of molecules possible, in ice only vibration;
in liquid there is sufficient energy/vibration (from latent heat) to break and re-form inter-molecular bonds;

(ii) mass of ice=70000×35000×240×920(=5.4×1014kg);
energy to raise ice temperature to 0°C=5.4×1014×2.1×103×35(= 3.98×1019J);
energy to melt ice=5.4×1014×3.3×105(=1.8×1020J);
total= 2.2×1020J

(iii) energy incident=450×70000×35000(=1.1×1012Js–1m−2);
energy available for melting=1.1×1012×0.2(=2.2×1011J);
time $$= \left( {\frac{{2.2 \times {{10}^{20}}}}{{2.2 \times {{10}^{11}}}} = } \right)9.9 \times {10^8}{\rm{s}}$$ or 32 years;

b.

average albedo of ocean much smaller than (snow and) ice;
so average albedo (of Earth) is reduced;


text:
# Syntactical proof of universal instantiation rule

First: I am not mathematician but philosopher. I understand why the universal instantiation rule is working.

$$\frac{\vdash\forall xA}{\vdash A^x_t}$$

But is there actually a serious proof in a logical proof system (Hilbert etc.) ? I don't personally find the critical step on how to get rid of the universal quantifier from one to the next line.

An idea of a syntactical proof:

1: $$\vdash\forall A$$

2: $$\vdash\forall A\to A$$

3: $$\vdash A$$

The first is the assumption, the second is a fact which I found in a book and which seems serious and the third line is modus ponens on the first two. But now, I have got the same result, but without the substitution in A?

• So, does this mean, my proof is correct, if I just put (x/t) at the last A in line 2 and at the A in line 3? – DORpapst May 11 at 17:19
• @FranzFerdinand For the purposes of producing a formal proof, it does not make sense to pick particular "facts" (theorems) from books. A formal proof is relative to a proof system. It takes work to show that two proof systems produce the same set of theorems (and they don't need to!), and even when you know that, the proofs will still look different. In many proof systems the rule you want to "seriously prove" is taken as a basic rule of inference. I seriously doubt producing a proof in a Hilbert-style proof system is going to be particularly enlightening or convincing. – Derek Elkins May 11 at 19:20
• I think another way to say what you are asking is "is there an established logic where UI is provable but not a primitive rule of inference?" – DanielV May 12 at 14:01
• @DanielV yes, that’s exactly what I meant here. – DORpapst May 14 at 12:10
• Off the top of my head, Godel's paper where he introduced his incompleteness theorem used $\exists$ $\lor$ and $\lnot$ as primitives, so it might not have had UI as a primitive. I don't exactly recall. But if so, UI would have been derived from negation rules, $\exists$-intros, $\exists$-elim, and $\forall x.P \equiv \lnot \exists x.\lnot P$ – DanielV May 15 at 6:32

## 1 Answer

The rule of Universal instantiation simply formalizes the evident intuitive principle that "what holds of all, holds of any"

In other words, if property $$A$$ holds of every object in the "universe" (this means $$\forall x A(x)$$), then it holds also of the object named by $$t$$ (i.e. $$A(t)$$).

In Natural Deduction it is one of the basic rules for quantifiers.

In Hilbert-style proof system we can derive it from the quantifier axiom :

$$\forall x A \to A^x_t$$.

• Hi, Thanks for your answer! I understand this semantical idea, that helps a lot. But my question actually deals more on the syntax. I have added some additional information and my thoughts in the question now. – DORpapst May 11 at 17:06


text:
# TikZ picture overlaps with text

I have a TikZ picture that overlaps with the text. I'm sure this one is easy, but I didn't find a solution.

Here is a snapshot:

And this is the code:

\section{Algorithm Outline}

blabla

\begin{figure}[H]
\selectlanguage{american}%
\begin{centering}
\ttfamily

\begin{tikzpicture}[node distance = 2cm,
auto, x=1cm, y=1cm,  transform canvas={scale=0.62},
>=stealth]
[picture code]

\end{tikzpicture}
\par\end{centering}

\selectlanguage{english}%
\caption{Algorithm Outline}
\end{figure}

The focus of this paper is on finding a feasible and good ....

I hope someone has a solution.

This post is slightly different than TikZ picture overlaps with text (not wanted)

-
This is most likely because you're using transform canvas, which causes PGF to "[lose] track of positions of nodes and of picture sizes" (PGF manual). I would try setting scale=0.62, every node/.append style={transform shape}, but it's hard to test without some TikZ code. –  Jake Feb 11 '13 at 16:15
What's the purpose of the two \selectlanguage commands? In the standard setup, american and english do exactly the same. Note also that \centering is not an environment; just put \centering instead of \begin{centering} and remove \par\end{centering} –  egreg Feb 11 '13 at 16:36
@Jake: I tried your suggestion, unfortunately it does not work. Maybe there is another solution to scale the whole picture. Like in pstricks, where one can set the unit to a value like 0.5cm. –  Chris Feb 11 '13 at 16:53
@Chris: Yes, there's that option, and you're already using it to set your unit vectors to 1cm length (which is the default value). Could you specify what you mean with "it does not work"? –  Jake Feb 11 '13 at 16:56
@Jake: sorry for not being specific. I meant that there is no change, but in fact I made a mistake. Your solution does work! Thanks a lot! –  Chris Feb 11 '13 at 17:14

This happens because you're using transform canvas, which causes PGF to "[lose] track of positions of nodes and of picture sizes" (PGF manual).

Set scale=0.62, every node/.append style={transform shape} to use the "proper" way to scale your tikzpicture.

-


text:
## 1.6. Functional Groups

### Learning Outcomes

• Describe the importance and purpose of functional groups in organic reactions.
• Identify and name functional groups in compounds.

With over twenty million known organic compounds in existence, it would be very challenging to memorize chemical reactions for each one. Fortunately, molecules with similar functional groups tend to undergo similar reactions.  Functional groups are structural units within organic compounds that are defined by specific bonding arrangements between specific atoms.  For example the structure of capsaicin, found in chili peppers, incorporates several functional groups, labeled in the figure below and explained throughout this section.

Even if other parts of the molecule are quite different, certain functional groups tend to react in certain ways.  As we progress in our study of organic chemistry, it will become extremely important to be able to quickly recognize the most common functional groups, because they are the key structural elements that define how organic molecules react.  For now, we will only worry about drawing and recognizing each functional group, as depicted by Lewis and line structures.  Much of the remainder of your study of organic chemistry will be taken up with learning about how the different functional groups behave in organic reactions.

The ‘default’ in organic chemistry (essentially, the lack of any functional groups) is given the term alkane, characterized by single bonds between carbon and carbon, or between carbon and hydrogen.  Methane, CH4, is the natural gas you may burn in your furnace.  Octane, C8H18, is a component of gasoline.

### Alkanes

Alkenes (sometimes called olefins) have carbon-carbon double bonds, and alkynes have carbon-carbon triple bonds.  Ethene, the simplest alkene example, is a gas that serves as a cellular signal in fruits to stimulate ripening.  (If you want bananas to ripen quickly, put them in a paper bag along with an apple – the apple emits ethene gas, setting off the ripening process in the bananas). Ethyne, commonly called acetylene, is used as a fuel in welding blow torches.

### Alkenes and alkynes

Later, we will study the nature of the bonding on alkenes and alkynes, and learn that that the bonding in alkenes is trigonal planar in in alkynes is linear.  Furthermore, many alkenes can take two geometric forms: cis or trans. The cis and trans forms of a given alkene are different molecules with different physical properties because, as we will learn in chapter 2, there is a very high energy barrier to rotation about a double bond. In the example below, the difference between cis and trans alkenes is readily apparent.

We will have more to say about the subject of cis and trans alkenes in chapter 3, and we will learn much more about the reactivity of alkenes in chapter 10.

Alkanes, alkenes, and alkynes are all classified as hydrocarbons, because they are composed solely of carbon and hydrogen atoms. Alkanes are said to be saturated hydrocarbons, because the carbons are bonded to the maximum possible number of hydrogens  – in other words, they are saturated with hydrogen atoms.  The double and triple-bonded carbons in alkenes and alkynes have fewer hydrogen atoms bonded to them – they are thus referred to as unsaturated hydrocarbons.

The aromatic group is exemplified by benzene (which used to be a commonly used solvent in the organic lab, but which was shown to be carcinogenic), and naphthalene, a compound with a distinctive ‘mothball’ smell. Aromatic groups are planar (flat) ring structures, and are widespread in nature.  We will learn more about the structure and reactions of aromatic groups next semester.

### Aromatics

When the carbon of an alkane is bonded to one or more halogens, the group is referred to as a alkyl halide or haloalkane.  Chloroform is a useful solvent in the laboratory, and was one of the earlier anesthetic drugs used in surgery. Chlorodifluoromethane was used as a refrigerant and in aerosol sprays until the late twentieth century, but its use was discontinued after it was found to have harmful effects on the ozone layer. Bromoethane is a simple alkyl halide often used in organic synthesis. Alkyl halides groups are quite rare in biomolecules.

### Haloalkanes

In the alcohol functional group, a carbon is single-bonded to an OH group (the OH group, by itself, is referred to as a hydroxyl). Except for methanol, all alcohols can be classified as primary, secondary, or tertiary.  In a primary alcohol, the carbon bonded to the OH group is also bonded to only one other carbon.  In a secondary alcohol and tertiary alcohol, the carbon is bonded to two or three other carbons, respectively. When the hydroxyl group is directly attached to an aromatic ring, the resulting group is called a phenol. The sulfur analog of an alcohol is called a thiol (from the Greek thio, for sulfur).

### Alcohols, phenols, and thiols

Note that the definition of a phenol states that the hydroxyl oxygen must be directly attached to one of the carbons of the aromatic ring. The compound below, therefore, is not a phenol – it is a primary alcohol.

The distinction is important, because as we will see later, there is a significant difference in the reactivity of alcohols and phenols.

We are already familiar with several common alcohols. For example, ethanol $\left( \ce{CH_3CH_2OH} \right)$ is the alcohol present in alcoholic beverages. It is also widely used in the industrial manufacture of other chemicals. Methanol $\left( \ce{CH_3OH} \right)$ is used as a gasoline additive or alternative. Additionally, methanol can be used to manufacture formaldehyde, which is employed in the production of plastics, paints, and other useful substances. Isopropanol is commonly known as rubbing alcohol. In addition to its industrial uses, isopropanol is used to clean various surfaces, including computer monitors, whiteboards, and even skin (e.g., before getting blood drawn).

The deprotonated forms of alcohols, phenols, and thiols are called alkoxides, phenolates, and thiolates, respectively. A protonated alcohol is an oxonium ion.

In an ether functional group, a central oxygen is bonded to two carbons. Below is the structure of diethyl ether, a common laboratory solvent and also one of the first compounds to be used as an anesthetic during operations. Ethers are good solvents for other organic compounds because of their low reactivity. They readily dissolve nonpolar molecules. The sulfur analog of an ether is called a thioether or sulfide.

### Ethers and sulfides

Amines are characterized by nitrogen atoms with single bonds to hydrogen and carbon. Just as there are primary, secondary, and tertiary alcohols, there are primary, secondary, and tertiary amines. Ammonia is a special case with no carbon atoms.

One of the most important properties of amines is that they are basic, and are readily protonated to form ammonium cations. In the case where a nitrogen has four bonds to carbon (which is somewhat unusual in biomolecules), it is called a quaternary ammonium ion.

Many smaller amines have very strong and offensive odors. For example, the aptly-named compounds cadaverine and putrescine are foul-smelling amines, formed as a part of the decay process after death.

Amines serve a wide variety of uses. Diphenylamine acts as a stabilizer for certain types of explosives. Amines are found as components in some lubricating materials, in developers, and are a part of waterproofing textiles. Some amines, such as novocaine, are used as anesthetics. Many pharmaceutical compounds contain amines, including 8 of the 10 most prescribed medications in 2012.

### Amines

Note: Do not be confused by how the terms ‘primary’, ‘secondary’, and ‘tertiary’ are applied to alcohols and amines – the definitions are different.  In alcohols, what matters is how many other carbons the alcohol carbon is bonded to, while in amines, what matters is how many carbons the nitrogen is bonded to.

Phosphate and its derivative functional groups are ubiquitous in biomolecules.  Phosphate linked to a single organic group is called a phosphate ester; when it has two links to organic groups it is called a phosphate diester.  A linkage between two phosphates creates a phosphate anhydride

### Organic phosphates

There are a number of functional groups that contain a carbon-oxygen double bond, which is commonly referred to as a carbonyl.   Ketones and aldehydes are two closely related carbonyl-based functional groups that react in very similar ways.  In a ketone, the carbon atom of a carbonyl is bonded to two other carbons.  In an aldehyde, the carbonyl carbon is bonded on one side to a hydrogen, and on the other side to a carbon.  The exception to this definition is formaldehyde, in which the carbonyl carbon has bonds to two hydrogens.

The simplest aldehyde has a carbonyl group bonded to two hydrogen atoms. This molecule, called formaldehyde, can be used as a tissue preservative or as a very harsh disinfectant. It is also used as a precursor to various materials, including plastics, resins, and other polymers.

Ketones undergo most of the same reactions as aldehydes, but they tend to be slightly less reactive. The simplest ketone is acetone, in which the carbonyl carbon is bonded to two $\ce{CH_3}$ groups. This ketone is commonly used to remove fingernail polish and serves as an industrial solvent. Methyl ethyl ketone is used as a paint stripper and a solvent. Ketones are also used in the production of various polymers, either as a building block or as a solvent.

A group with a carbon-nitrogen double bond is called an imine, or sometimes a Schiff base (in this book we will use the term ‘imine’).

### Aldehydes, ketones, and imines

When a carbonyl carbon is bonded on one side to a carbon (or hydrogen) and on the other side to an oxygen, nitrogen, or sulfur, the functional group is considered to be one of the ‘carboxylic acid derivatives’, a designation that describes a set of related functional groups.  The eponymous member of this family is the carboxylic acid functional group, in which the carbonyl is bonded to a hydroxyl group.   The conjugate base of a carboxylic acid is a carboxylate

As the name implies, carboxylic acids are weak acids. An $\ce{OH}$ group that is directly connected to a carbonyl will ionize to a small extent when dissolved in water. because of the relative stability of the resulting anion. A carboxylate ion (see figure below), in which the negative charge is spread over two different oxygen atoms through resonance structures, is more stable than an isolated oxygen-centered anion.

Carboxylic acids are used in a variety of environments. Formic acid acts as a protective chemical for many stinging insects and plants. Acetic acid gives vinegar its characteristic smell and flavor and is a fundamental biological and industrial building block. Carboxylic acids with longer carbon chains (fatty acids) are used by animals as a way of storing energy and are widely used in the manufacture of soaps. Some compounds contain multiple carboxylic acids within a single molecule. For example, citric acid (three carboxyl groups) is especially abundant in citrus fruits and it used as a flavoring and preservative in many foods and beverages.

Other derivatives are carboxylic esters (usually just called ‘esters’), thioesters, amides, acyl phosphates, acid chlorides, and acid anhydrides.  With the exception of acid chlorides and acid anhydrides, the carboxylic acid derivatives are very common in biological molecules and/or metabolic pathways.

Esters are very important in synthesis and in nature.  Some esters have very pleasant odors, so they are used in the manufacture of many perfumes. Propyl acetate contributes to the odor of pears, while isoamyl acetate gives bananas their smell. This ester also serves as an alarm signal for honeybees. Esters are employed in the manufacture of fabrics (polyesters) and Plexiglass. Anesthetics such as procaine and benzocaine also contain esters.

The amide group forms is extremely important in biological systems, where it is called a “peptide”, used for linking amino acids together to form polypeptides and (ultimately) proteins.  Amides are used as coloring agents in crayons, pencils, and ink. They are employed in the paper, plastic, and rubber industries. Polyacrylamide is a very widely used amide; it is involved in t he treatment of drinking water and sewage, and in plastics manufacture. The amide Kevlar is widely employed for the production of body armor, and nylon is another type of amide-based polymer.

### Carboxylic acid derivatives

Finally, a nitrile group is characterized by a carbon triple-bonded to a nitrogen.

### Nitriles

A single compound often contains several functional groups, particularly in biological organic chemistry.  The six-carbon sugar molecules glucose and fructose, for example, contain aldehyde and ketone groups, respectively, and both contain five alcohol groups (a compound with several alcohol groups is often referred to as a ‘polyol’).

The hormone testosterone, the amino acid phenylalanine, and the glycolysis metabolite dihydroxyacetone phosphate all contain multiple functional groups, as labeled below.

While not in any way a complete list, this section has covered most of the important functional groups that we will encounter in synthetic and biological organic chemistry.   A summary table is included in your workbook, and is reproduced here for reference; the “priority” is used when determining how to name a compound with multiple functional groups.  We will formally learn how to name functional groups later.

Priority order for functional groups in IUPAC nomenclature

 Functional Group Family Functional Group Structure Name if main group Name if substituent Carboxylic acid alkanoic acid carboxy Ester alkyl alkanoate alkoxycarbonyl Amide alkanamide amido Nitrile alkanenitrile cyano Aldehyde alkanal formyl Ketone alkanone oxo Alcohol alkanol hydroxy Amine alkanamine amino Alkene alkene alkenyl Alkyne alkyne alkynyl Alkane alkane alkyl Ether alkoxy Halide halo Nitro compound nitro

### EXERCISE 1.12

Identify the functional groups (other than alkanes) in the following organic compounds. State whether alcohols and amines are primary, secondary, or tertiary.

Solutions to exercises

### Exercise 1.13

Draw one example each of compounds fitting the descriptions below, using line structures.  Be sure to designate the location of all non-zero formal charges. All atoms should have complete octets (phosphorus may exceed the octet rule). There are many possible correct answers for these, so be sure to check your structures with your instructor or tutor.

a) a compound with molecular formula C6H11NO that includes alkene, secondary amine, and primary alcohol functional groups

b) an ion with molecular formula C3H5O6P 2- that  includes aldehyde, secondary alcohol, and phosphate functional groups.

c) A compound with molecular formula C6H9NO that has an amide functional group, and does not have an alkene group.

Khan Academy video tutorial on functional groups:


text:
# lay down

## Definitions

• Now I Lay Me Down to Sleep 094
• WordNet 3.6
• v lay down institute, enact, or establish "make laws"
• ***

She lay down on the bed of the Little, Small, Wee Bear

Chambers's Twentieth Century Dictionary
• Interesting fact: When ants find food, they lay down a chemical trail, called a pheromone, so that other ants can find their way from the nest to the food source.
• Lay down to give up: to deposit, as a pledge: to apply, as embroidery: to delineate, describe: to affirm, assert:
• Lay down (rare) to store for future use
• ***

## Quotations

• Jon English
“You can lay down and die, or you can get up and fight, but that's it -- there's no turning back.”
• John Milton
“How gladly would I meet mortality, my sentence, and be earth in sensible! how glad would lay me down, as in my mother's lap! There I should rest, and sleep secure.”
• Woody Allen
“The lion and the calf will lay down together, but the calf won't get much sleep..”
• Bible
“Greater love hath no man than this, that a man lay down his life for his friends. [Jhn 15:13]”
• Eric Hoffer
“There is probably an element of malice in the readiness to overestimate people; we are laying up for ourselves the pleasure of later cutting them down to size.”

## Idioms

Lay down the law - If someone lays down the law, they tell people what to do and are authoritarian.
***

## Etymology

Chambers's Twentieth Century Dictionary
Lay is the causal to lie, from A.S. lecgan; Ice. leggja, Ger. legen.

## Usage

### In literature:

After supper was over, and we had dried our clothes, wet through and through by the spray, we lay down to sleep under the rock.
"Peter Trawl" by W. H. G. Kingston
Small fires only were formed, around which we lay down to sleep.
"Snow Shoes and Canoes" by William H. G. Kingston
We ourselves were glad to get some rest, and lay down in the shade to wait until evening, when we proposed building the raft.
"The Two Supercargoes" by W.H.G. Kingston
We all went below and lay down, hoping to get a little sleep and rest before it was time to start.
"Will Weatherhelm" by W.H.G. Kingston
After dat us went off to lay down fer de night.
"Slave Narratives Vol. XIV. South Carolina, Part 2" by Works Projects Administration
Ready was soon dressed, for he had only taken off his jacket when he lay down.
"Masterman Ready" by Captain Frederick Marryat
I lay down, and I did not wake till she called me and told me that dinner was ready.
"The Privateersman" by Frederick Marryat
When finally Tim lay down his paddle and rested they were charmed.
"Adrift in the Wilds" by Edward S. Ellis
He lay down on the ice to laugh, and rolled about as if he had the bowel-twist.
"The Giant of the North" by R.M. Ballantyne
Here we lay down, awaiting developments.
"The Trail of '98" by Robert W. Service
After walking a long time and meeting nothing he became tired, and lay down on a knoll where the sun had melted the snow.
"Folk-Lore and Legends: North American Indian" by Anonymous
It lay down to sleep on the bare floor; she lay on the bench.
"Russian Fairy Tales" by W. R. S. Ralston
As the Father knoweth me, even so know I the Father: and I lay down my life for the sheep.
"Jesus the Christ" by James Edward Talmage
Here he lay down a second time and within five minutes had fallen into a deep sleep.
"The Highgrader" by William MacLeod Raine
On the fifth night I undressed and lay down as usual.
"At the Point of the Sword" by Herbert Hayens
When we reached the sea-shore, we all ran and lay down among the waves.
"Perils and Captivity" by Charlotte-Adélaïde [née Picard] Dard
Overcome with fatigue, he lay down to rest a little, and, as was very natural, fell fast asleep.
"The Rival Crusoes" by W.H.G. Kingston
Meanwhile, with little catching sobs, which he struggled to repress, the boy lay down in his crib.
"The Manxman A Novel - 1895" by Hall Caine
When he gave us rest she was clean out of sight, and we lay down in the bushes and loafed for a while.
"At Plattsburg" by Allen French
After dinner was over the old woman lay down on the bed.
"Tales of Folk and Fairies" by Katharine Pyle
***

### In poetry:

And the winds woke, and the storm broke,
And wrecks came plunging in;
None in the town that night lay down
Or sleep or rest to win.
"Winstanley" by Jean Ingelow
They lay the slender body down
With all its wealth of wetted hair,
Only a daughter of the town,
But very young and slight and fair.
"Story Of Lilavanti" by Laurence Hope
Bring flowers when her soul has fled,
And place them on her breast,
Tho' ere their blooming freshness fade
We lay her down to rest.
"Flowers" by William James Jones
Our path lay through the sunny fields,
In gentle ups and downs;
Dear heart! I thought, but nature yields
A bliss unmatch'd in towns.
"A Walk To Pamphy Linns" by Alexander Anderson
"The rings that are on your fingers,
Lay them down on a stane,
To let him know, when he does wake,
That's true love's come and gane.
"The Broomfield Hill" by Andrew Lang
O! after all the toils of war,
How blest the brave man lays him down!
His bier is a triumphal car—
His grave is—glory and renown!
"The Muffled Drum" by John Mayne

### In news:

Administration Lays Down Rules For Future Health Insurance.
Dirt Dogg has been laying it down for Middle GA for over ten years.
Dan will be laying down another list today.
A Senate Democratic leader lays down a partisan 2013 marker.
Lay the eggplants on the baking sheet, cut side down, and place in the oven for 20 minutes, or until the skin has shriveled and the eggplants are beginning to collapse.
It's time for the Rangers to lay down a Game 6 hammer on the Capitals and put an end to this conference.
Check out his promising debut video that's gone viral, where he lays down some slick verses that have absolutely no meaning.
Gonna Lay Me Down Beside My Memories.
I Lie Down vs Now I Lay Me Down (to Sleep).
A woman lays down a flower during the inaugural ceremony of the memorial to the murdered European Sinti and Roma who were persecuted as ' Gypsies ' in Berlin, Wednesday, Oct 24, 2012.
Laying down the law on hamster disorder.
And lay their money down.
The show was loud and loose as always, with Paul Morabito laying down some fantastic guitar.
Your dog can fetch, lay down and play dead but can it sit .
Laying down the slaw .
***

### In science:

Lay down in random order a row of n cards numbered from 1 to n.
When the law of large numbers fails for increasing subsequences of random permutations
The explicit frequency domain parametrization of the proposed template family makes it easier to adopt the formalism proposed by Owen in laying down the templates using a metric in the parameter space.
A template bank for gravitational waveforms from coalescing binary black holes: non-spinning binaries
Section II lays down some necessary de ﬁnitions.
Asymptotic Eigenvalue Moments of Wishart-Type Random Matrix Without Ergodicity in One Channel Realization
Thus one can essentially lay down a new i.i.d. environment at each of these cut-times.
Excited against the tide: A random walk with competing drifts
We count the ways to lay down an ordered pair of 3-star factors in P ∈ Pn,d .
The Asymptotic Distributions of 3-star factors in random d-regular graphs
In the ﬁrst part we lay down the foundation for deﬁning the joint annihilation–preservation– creation decomposition of a ﬁnite family of, not necessarily commutative random variables, and show that this decomposition is essentially unique.
Two dimensional Meixner random vectors of class ${\mathcal M}_L$
The lesson is to police the observer’s evaluation process, laying down some optimal rules for a human observer.
Definability in the Real Universe
Our second contribution is laying down the foundations of a concept that we call Knowledge-Enhanced Compressive Sensing (KECoM) for sub-Nyquist sampling, which we preliminarily explored in with limited numerical experiments.
A Constrained Random Demodulator for Sub-Nyquist Sampling
We try to lay down the foundations of a Newtonian theory where inertia and gravitational ﬁelds appear in a uniﬁed way aiming to reach a better understanding of the general relativistic theory.
Rigid motions and generalized Newtonian gravitation. Lost in Translation
As we approach the neolithic, the ﬁrst plant to lay down its life for a noodle was millet (Anonymous 2006m).
Astrophysics in 2006
If you lay the paper down on a table, you can’t stretch it along the direction of the paper (it would tear).
A Simple Introduction to Particle Physics Part II
This study also lays down the foundations for reheating in inﬂationary models where the inﬂaton couples to all the degrees of freedom with the Standard Model gauge couplings.
Non-perturbative production of matter and rapid thermalization after MSSM inflation
In Section 2 we lay down some of the necessary foundational material for the theory of 1-skeleta, closely following Guillemin and Zara .
Generalized 1-skeleta and a lifting result
The paper also lays down the geometric foundations for our paper concerning gluing constructions for SL conifolds in Cm .
Special Lagrangian conifolds, I: Moduli spaces (extended version)
More importantly, it lays down the geometric foundations for ; the analytic foundations are provided by .
Special Lagrangian conifolds, I: Moduli spaces (extended version)
***


text:
Toeplitz Block Matrices in Compressed Sensing

# Toeplitz Block Matrices in Compressed Sensing

Florian Sebert, Leslie Ying, and Yi Ming Zou
01/10/2008
###### Abstract.

Recent work in compressed sensing theory shows that independent and identically distributed (IID) sensing matrices whose entries are drawn independently from certain probability distributions guarantee exact recovery of a sparse signal with high probability even if . Motivated by signal processing applications, random filtering with Toeplitz sensing matrices whose elements are drawn from the same distributions were considered and shown to also be sufficient to recover a sparse signal from reduced samples exactly with high probability. This paper considers Toeplitz block matrices as sensing matrices. They naturally arise in multichannel and multidimensional filtering applications and include Toeplitz matrices as special cases. It is shown that the probability of exact reconstruction is also high. Their performance is validated using simulations.

F. Sebert and Y. M. Zou are with the Department of Mathematical Sciences, University of Wisconsin, Milwaukee, WI 53201, USA email: fmsebert@uwm.edu, ymzou@uwm.edu
L. Ying is with the Department of Electrical Engineering, University of Wisconsin, Milwaukee, WI 53201, USA email: leiying@uwm.edu

## 1. Introduction

The central problem in compressed sensing (CS) is the recovery of a vector from its linear measurements of the form

 (1.1) yi=,1≤i≤n,

where is assumed to be much smaller than . Of course, for , (1.1) posts an under-determined system of equations which has non-unique solutions. Exact recovery of the original vector needs further prior information. The work by Candés, Donoho, Romberg, Tao, and others (see e.g. [1],[2], and the references therein) showed that under the assumption that is sparse, one can actually recover from a sample which is much smaller in size than by solving a convex program with a suitably chosen sampling basis . If we write the linear system (1.1) in the form

 (1.2) y=Φx,where Φ is an n×N matrix,

then the question about what sampling methods guarantee the exact recovery of becomes the question about what matrices are “good” compressed sensing matrices, meaning that they ensure exact recovery of a sparse from with high probability under the condition that .

In [3] Candès and Tao introduce the restricted isometry property as a condition on matrices which provides a guarantee on the performance of in compressed sensing.

Following their definition, we say that a matrix satisfies RIP of order and constant if

 (1.3) (1−δm)∥z∥22≤∥ΦTz∥22≤(1+δm)∥z∥22∀z∈R|T|,

where , , and denotes the matrix obtained by retaining only the columns of corresponding to the entries of .

It was shown in [3] (reinterpreted in [4]) that if satisfies RIP of order and constant :

 (1.4) (1−δ3m)∥z∥22≤∥ΦTz∥22≤(1+δ3m)∥z∥22∀z∈R|T|,

where and , the decoder given by

 (1.5) △(y):=argmin∥x∥lN1      subject to  Φx=y

ensures exact recovery of from .

Recently Baraniuk et al [5] showed that matrices whose entries are drawn independently from certain probability distribution satisfy RIP of order with probability for every provided that , where are some positive constants depending only on . Motivated by applications in signal processing, Bajwa et al [6] considered (truncated) Toeplitz-structured matrices whose entries are drawn from the same probability distributions and showed that they satisfy RIP of order with probability for every provided that .

Some examples of probability distributions that can be used in this context have been studied in [7]. They include

 ri,j∼N(0,1n),
 (1.6) ri,j=⎧⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪⎩1√nwith % probability1/2−1√nwith probability1/2,
 ri,j=⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩√3nwith % probability1/60with probability2/3−√3nwith probability1/6.

Motivated by applications in multichannel sampling, in this paper we will consider Toeplitz block matrices with elements in each block drawn independently from one of the probability distributions in (1.6) and some other block matrices with similar structures. We show that such matrices also satisfy RIP of order for every with high probability, provided that , where and is some positive constant depending only on . These Toeplitz block matrices naturally represent the system equation matrices in multichannel sampling applications where a single input signal is recovered from output samples of multiple channels with IID random filters. The result justifies the use of multichannel over single-channel systems in compressed sensing. The advantages of Toeplitz matrices pointed out in [6], like e.g. efficient implementations, also apply to the matrices considered in this paper.

## 2. Main Result

###### Theorem 2.1.

For Toeplitz block matrices of the form

 (2.1) Φ=⎛⎜ ⎜ ⎜ ⎜ ⎜⎝ΦkΦk−1…Φ2Φ1Φk+1Φk…Φ3Φ2⋮⋮⋱⋱⋮Φk+l−1Φk+l−2……Φl⎞⎟ ⎟ ⎟ ⎟ ⎟⎠∈Rn×N

with blocks whose elements are drawn independently from one of the probability distributions in (1.6), there exist constants depending only on , such that:

1. If , then for any , satisfies RIP of order for every with probability at least

 1−e−c2n/l.
2. If , then for any , satisfies RIP of order for every with probability at least

 1−e−c2n/m2.

The above theorem gives the requirement for and probability of exact reconstruction of a -sparse signal from a measurement if Toeplitz block matrices are used. In particular it says, that if the number of blocks () in one column of does not exceed a certain value depending only on the sparsity of the signal , the probability of perfect reconstruction is greater and the number of required measurements is smaller than if is not bounded in this way.

As noted in [6, 9], Toeplitz matrices naturally arise in one-dimensional single-channel filtering applications where the matrix elements are filter coefficients. Similarly, the Toeplitz block matrices defined in (2.1) naturally arise in one-dimensional multichannel sampling applications where the length of the filter is at least points larger than that of the input signal. The conventional multichannel sampling theorem states that the sampling rate reduction over the single channel system cannot exceed the number of channels for exact recovery. While Theorem 2.1 suggests that multichannel systems with IID random filters might be able to reduce the sampling rate by a factor higher than the number of channels.

We remark, that for other block matrices with similar structures, the result in Theorem 2.1 also holds (see IV).

## 3. Proof of Main Result

Let . Denote by the -th row of the matrix obtained by retaining only those columns of corresponding to the elements in , and let denote the set of random variables common to the -th row of and the -th block of .

We note that, if (1.4) holds for a set , then it also holds for any . To prove that Toeplitz IID block matrices satisfy RIP with high probability, it is therefore enough to consider only those sets where .

###### Lemma 3.1.

Define the sets by

 DT,i={j∈{1,2,…,n}:ΦT,j is stochastically dependent on% ΦT,i,j≠i}.
• If satisfies , then

• If satisfies , then

###### Proof.

Fix . defines a sequence , where is the number of columns from block in . Thus . Consider the number of rows that have dependency with the elements in . Since all elements inside a single block are independent, there can be no dependencies within one block. Moreover, because of the structure of the matrix , there can be at most

 {0if Φts∩ΦT,i=∅|T|−rtsif Φts∩ΦT,i≠∅

rows outside the block that depend on any element in .
(i) If satisfies , i.e. if , these rows may be distinct, and we have

 |DT,i| ≤∑{ts,s∈{1,2,…,k}:Φts∩ΦT,i≠∅}(|T|−rts) ≤∑t∈T(|T|−1)=|T|(|T|−1)≤l−1

dependent rows.
(ii) If satisfies , i.e. if , then is upper bounded by the number of blocks, so .

In [7] it has been shown that for given , , and with , an IID matrix of size with entries drawn independently from one of the distributions in (1.6)111These matrices consist of columns whose squared norm is equal to 1 in expectation. satisfies (1.3) with probability

 (3.1) ≥1−e−f(n,m,δm),

where

 (3.2) f(n,m,δm)=c0n−mln(12/δm)−ln(2).

Now consider a (truncated) Toeplitz block matrix as in (2.1), where the blocks are such IID matrices with entries drawn independently from the same set of distributions as above.

The following lemma gives an upper bound for the probability that a matrix as in (2.1) with satisfies (1.4) for any fixed subset with . Lemma 3.3 gives a tighter bound for the case .

The proof of Lemma 3.2 uses an argument similar to the one in the proof of Lemma 1 in [6].

###### Lemma 3.2.

For given with , and , the Toeplitz block submatrix satisfies (1.4) with probability at least

 1−e−f(d,m,δm)+ln(l).
###### Proof.

We can write the matrix as

 (3.3) ΦT=⎛⎜ ⎜⎝Φ1T⋮ΦlT⎞⎟ ⎟⎠,

where the blocks of size are given by the columns determined by in the -th row of blocks in .

Note that is an IID matrix with entries from one of the distributions in (1.6). If we let , then the matrices have columns whose squared norm is equal to 1 in expectation and by (3.1) satisfy (1.4), i.e.

 (1−δm)∥z∥22≤∥~ΦiTz∥22≤(1+δm)∥z∥22, ∀z∈R|T|, ∀i∈{1,2,…,l},

with probability at least

 (3.4) 1−e−f(d,m,δm).

Now since

 (3.5) ∥ΦTz∥22=l∑i=1∥ΦiTz∥22=l∑i=11l∥~ΦiTz∥22

and , we have

 (1−δm)∥z∥22≤∥ΦTz∥22≤(1+δm)∥z∥22,∀z∈R|T|.

In other words, the event implies the event
. Consequently,

 P(E2) =1−P(Ec2)≥1−P(Ec1) ≥1−l∑i=1P({~ΦiT does not % satisfy (???)}) ≥1−l∑i=1e−f(d,m,δm)(by (???)) =1−e−f(d,m,δm)+ln(l).

###### Lemma 3.3.

For given with , and , if , the Toeplitz block submatrix satisfies (1.4) with probability at least

 1−e−f(⌊n/q⌋,m,δm)+ln(q),

where .

###### Proof.

Let denote the -th row of and construct an undirected dependency graph such that and

 E={(i,i′)∈V×V:i≠i′,ΦT,i and ΦT,i′ are dependent}.

By Lemma 3.1, can at most be dependent with other rows. Therefore, the maximum degree of is given by , and using the Hajnal-Szemerédi theorem on equitable coloring of graphs, we can partition using colors. Let be the different color classes, then

 |Cj|=⌊n/q⌋ or |Cj|=⌈n/q⌉.

Now, let be the submatrix obtained from retaining the rows corresponding to the indices in and define . Then

 (3.6) ∀z∈R|T|,∥ΦTz∥22=q∑j=1∥ΦjTz∥22=q∑j=1|Cj|n∥~ΦjTz∥22.

Every is a IID matrix whose columns have squared norm equal to 1 in expectation. By (3.1), they satisfy (1.4) with probability at least

 (3.7) 1−e−f(|Cj|,m,δm)≥1−e−f(⌊n/q⌋,m,δm).

Since , by (3.6), we have that if

 (1−δm)∥z∥22≤∥~ΦjTz∥22≤(1+δm)∥z∥22,∀z∈R|T|, ∀j∈{1,2,…,q}

then

 (1−δm)∥z∥22≤∥ΦTz∥22≤(1+δm)∥z∥22,∀z∈R|T|.

In other words, the event implies the event . Consequently,

 P(E2) =1−P(Ec2)≥1−P(Ec1) ≥1−q∑j=1P({~ΦjT does not % satisfy (???)}) ≥1−q∑j=1e−f(⌊n/q⌋,m,δm)(by (???)) =1−e−f(⌊n/q⌋,m,δm)+ln(q).

Main result in Theorem 2.1.

###### Proof.

(i) From (3.2) and Lemma 3.2 we have that satisfies (1.4) for any such that with probability at least

 (3.8) 1−e−c0d+3mln(12/δ3m)+ln(2)+ln(l).

Since there are such subsets, using Bonferroni’s inequality (see e.g. [8]) yields that satisfies RIP of order with probability at least

 (3.9) 1−e−c0n/l+3m[ln(12/δ3m)+ln(N/3m)+1]+ln(2)+ln(l).

Fix and pick . Then for any , the exponent of in (3.9) is upper bounded by :

 −c0nl+3m[ln(12δ3mN3m)+1]+ln(2l)≤−c2nl ⇔ 3m[ln(12δ3mN3m)+1]+ln(2l)≤nl(c0−c2) ⇔ 3lmc0−c2[ln(12δ3mN3m)+1+ln(2)3m+ln(l)3m]≤n ⇔ 3lmln(Nm)c0−c2⎡⎢ ⎢⎣ln(12δ3mN3m)+1+ln(2)+ln(l)3mln(Nm)⎤⎥ ⎥⎦≤n ⇐ 3lmln(Nm)c0−c2[ln(12δ3m)+5]≤n ⇔ c1lmln(Nm)≤n

(ii) From (3.2) and Lemma 3.3 we have that satisfies (1.4) for any such that with probability at least

 1−e−c0⌊n/q⌋+3mln(12/δ3m)+ln(2)+ln(q) (3.10) ≥ 1−e−c0n/9m2+3mln(12/δ3m)+ln(2)+ln(9m2)+c0.

Since there are such subsets, using Bonferroni’s inequality again yields that satisfies RIP of order with probability at least

 (3.11) 1−e−c0k/9m2+3m[ln(12/δ3m)+ln(N/3m)+1]+ln(2)+ln(9m2)+c0.

Now fix and pick , where . Then, for any , the exponent of in (3.11) is upper bounded by . This completes the proof of the theorem. ∎

###### Remark 3.1.

If , then is an IID matrix, and Theorem 2.1 lower bounds the probability of satisfying RIP of order by , which recovers the bound obtained in [5].

###### Remark 3.2.

As long as , a matrix as in (2.1) satisfies RIP of order with probability , which is the bound given in [6], since

 (3.12) −c2n/l≤−c2n/(9m2−3m)≤−c2n/9m2=−c′2n/m2.

## 4. Other Block Matrices

### 4.1. Circular matrices

The above consideration can be applied to (truncated) circulant block matrices of the form

 (4.1) Φ=⎛⎜ ⎜ ⎜ ⎜ ⎜⎝ΦkΦk−1…Φ2Φ1Φ1Φk…Φ3Φ2⋮⋮⋱⋱⋮Φl−1Φl−2……Φl⎞⎟ ⎟ ⎟ ⎟ ⎟⎠∈Rn×N,

where the blocks are all IID matrices.

Similar to (2.1), the circulant matrices in (4.1) also represent the system equation matrices in multichannel sampling, but the convolution is a circular one. They usually arise in applications where convolutions are implemented by multiplications in Fourier domain.

Before we present the theorem for this type of matrices, we first comment on the maximum number of stochastically dependent rows in a (truncated) circulant matrix of the form

 (4.2) A=⎛⎜ ⎜ ⎜ ⎜ ⎜⎝aqaq−1…a2a1a1aq…a3a2⋮⋮⋱⋱⋮ap−1ap−2……ap⎞⎟ ⎟ ⎟ ⎟ ⎟⎠∈Rp×q.

Again, we denote by the -th row of the matrix , which is obtained by retaining only those columns of corresponding to .

###### Lemma 4.1.

Define the sets by is stochastically dependent on Then has cardinality at most .

###### Proof.

Note first, that an upper bound for the case clearly upper bounds the case where . We may therefore assume that and is a square circulant matrix. Then the number of rows stochastically dependent on is independent of and we can, w.l.o.g., assume that . Let be a -tuple defined by

 tj={0if j∉T1if j∈T,j=1,\ldots,q,

and consider the matrix

 (4.3) ~A=⎛⎜ ⎜ ⎜ ⎜⎝tσ(t)…σq−1(t)⎞⎟ ⎟ ⎟ ⎟⎠∈Rq×q,

where defines the right-shift . Denote by the matrix obtained by retaining only those columns of corresponding to . It is now easy to see that

 |DT,i| =|{~AT,i,i∈{2,…,q} : h(~AT,1,~AT,i)<|T|}| ≤{# of ones in t}⋅({# of ones % in t}−1) =|T|(|T|−1),

where is the Hamming distance defined by

 h(x,y)=|{j∈{1,2,…,q} : xj≠yj}|.

The following theorem gives lower bounds for the probability that a circulant block matrix as in 4.2 satisfies the RIP of order . Note that the bounds obtained are the same as in 2.1 although the number of independent entries in is greater than before. This is due to the nature of the proof using the number of stochastically dependent rows of which is the same for both Toeplitz and circulant matrices.

###### Theorem 4.1.

Let be as in (4.1). Then there exist constants depending only on , such that:

1. If , then for any , satisfies RIP of order for every with probability at least

 1−e−c2n/l.
2. If , then for any , satisfies RIP of order for every with probability at least

 1−e−c2n/m2.
###### Proof.

A similar argument as the one in the proof of Lemma 3.1 shows that the upper bound for the maximum number of rows stochastically dependent on any row of a (truncated) circulant block matrix is the same as for the (truncated) Toeplitz block matrices (use Lemma 4.1). Then the proof of Theorem 2.1 directly applies to the setting at hand. ∎

### 4.2. Circulant-circulant Matrices

We also consider matrices that are (truncated) circulant block matrices whose blocks are themselves circulant:

 (4.4) Φ =⎛⎜ ⎜ ⎜ ⎜ ⎜⎝ΦkΦk−1…Φ2Φ1Φ1Φk…Φ3Φ2⋮⋮⋱⋱⋮Φl−1Φl−2……Φl⎞⎟ ⎟ ⎟ ⎟ ⎟⎠∈Rn×N, (4.5) Φi =⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝φipφip−1…φi2φi1φi1φip…φi3φi2⋮⋮⋱⋱⋮φiq−1φiq−2……φiq⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠∈Rq×p.

Denote by the right-shift of blocks and by the right-shift of elements inside a block , both by one position. These matrices arise in two-dimentional imaging applications where the independent elements are the coefficients of the point spread function of the imaging system. Replacing (4.3) in the proof of Lemma 4.1 by

 ¯A=⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝tσ1τ0(t)⋮σ(i−1)(mod p)τ⌊i−1p⌋(t)⋮σp−1τl−1(t)⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠∈Rlq×kp,

readily yields the upper bound for the number of rows stochastically dependent on any one row of . Applying Lemma 3.3 and Theorem 4.1 shows that the probability for perfect reconstruction is no less than . This says that imaging systems with IID random point spread functions can significantly reduce the number of acquired samples, while still being able to reconstruct the original sparse image if the above conditions hold.

### 4.3. Circulant-circulant Block Matrices

As a generalization of the matrices defined by (4.4) and (4.5), the following matrices are also considered:

 (4.6) Φ =⎛⎜ ⎜ ⎜ ⎜ ⎜⎝Φk1Φk1−1…Φ2Φ1Φ1Φk1…Φ3Φ2⋮⋮⋱⋱⋮Φl1−1Φl1−2……Φl1⎞⎟ ⎟ ⎟ ⎟ ⎟⎠∈Rn×N, Φi

where the blocks are all IID matrices. These matrices arise in multichannel two-dimensional imaging applications where the number of rows in corresponds to the independent channels. We show next that these matrices are also good compressed sensing matrices.

###### Corollary 4.1.

Let be as in (4.6). Then there exist constants depending only on , such that:

1. If , then for any , satisfies RIP of order for every with probability at least

 1−e−c2n/l1l2.
2. If , then for any , satisfies RIP of order for every with probability at least

 1−e−c2n/m2.

This follows directly from Lemma 4.1 and Theorem 4.1.

### 4.4. Deterministic Construction

The CS matrices we have considered so far are based on randomized constructions. However, in certain applications, deterministic constructions are preferred. In [10] DeVore provided a deterministic construction of CS matrices using polynomials over finite fields. We will consider deterministic block matrices based on DeVore’s construction. Let us first recall the construction in [10].

Consider the set , where denotes the field of integers modulo , a prime. This set has elements. Define , . This set has elements. For every , define the graph of by

and consider the column vector , indexed by the elements of ordered lexicographically, given by

 v(f):=(1(0,0)∈G(f),…,1(0,p−1)∈G(f),1(1,0)∈G(f),…,1(p−1,p−1)∈G(f))t,

where

 1(a,b)∈G(f)={1if (a,b)∈G(f)0if (a,b)∉G(f)

Construct the matrix , where the polynomials are ordered lexicographically with respect to their coefficients. It was shown in [10], that the matrix satisfies RIP for any with .

Now consider

 (4.7) Ψ0=⎛⎜ ⎜ ⎜ ⎜ ⎜⎝ΨtΨt−1…Ψ2Ψ1Ψt+1Ψt…Ψ3Ψ2⋮⋮⋱⋱⋮Ψt+s−1Ψt+s−2……Ψs⎞⎟ ⎟ ⎟ ⎟ ⎟⎠∈Rsp2×tl,

where , and each block is constructed from the first vectors , as above.

###### Theorem 4.2.

The matrix satisfies RIP with for any .

###### Proof.

As before, we only have to consider the case where . Let such that , and let be the matrix obtained by retaining only those columns of corresponding to the elements in . Consider the matrix . Since every column of has exactly ones, the diagonal elements of are all one. An off diagonal element of has the form , where , and denotes the vector that represents some polynomial . Since the graphs of two different polynomials in have at most elements in common, for any . Therefore, the sum of all off diagonal elements in any row or column of is whenever . We can, therefore, write

 (4.8) GT=I+BT,

where and . Since , we have that and so the spectral norms of and are and , respectively. This shows that satisfies (1.4). ∎

## 5. Numerical Results

To validate that the probability of exact recovery for Toeplitz block CS matrices is high, the performance of Toeplitz block, IID, and Toeplitz CS matrices is compared empirically. In our simulation, a length n = 2048 signal with randomly placed m = 20 non-zero entries drawn independently from the Gaussian distribution was generated. Each such generated signal is sampled using IID, Toeplitz and Toeplitz block matrices with entries drawn independently from the Bernoulli distribution and reconstructed using the log barrier solver from [11]. The experiment is declared a success if the signal is exactly recovered, i.e., the error is within the range of machine precision. The empirical probability of success is determined by repeating the reconstruction experiment 1000 times and calculating the fraction of success. This empirical probability of success is plotted as a function of the number of measurement samples n in Fig. 1. The simulation results show, that in the vast majority of applications all Toeplitz block matrices perform similar to IID matrices.

## Acknowledgment

The third author would like to acknowledge the support from IMA for his participation in the short course “Compressive Sampling and Frontiers in Signal Processing”.

## References

• [1] E. Candès, J. Romberg, and T. Tao, ”Robust uncertainty principles: Exact sinal reconstruction from highly incomplete frequency information”, IEEE Trans. Inf. Theory 52, no. 2, pp. 489-509, 2006.
• [2] D. Donoho, ”Compressed Sensing”, IEEE Trans. Information Theory 52, no. 4, pp. 1289-1306, 2006.
• [3] E. Candès and T. Tao, ”Decoding by linear programming”, IEEE Trans. Inf. Theory 51, no. 12, pp. 4203-4215, 2005.
• [4] A. Cohen, W. Dahmen, and R. DeVore, ”Compressed sensing and best k-term approximation”, (2006), Preprint.
• [5] R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, ”A Simple Proof of the Restricted Isometry Property for Random Matrices”, (2007), Preprint.
• [6] W. Bajwa, J. Haupt, G. Raz, S. Wright, and R. Nowak, ”Toeplitz-Structured Compressed Sensing Matrices”, IEEE SSP Workshop, pp. 294-298, 2007.
• [7] D. Achlioptas, ”Database-friendly Random Projections”, Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pp. 274-281, 2001.
• [8] Y. Dodge, F. Marriott, Int. Statistical Institute, ”The Oxford dictionary of statistical terms”, 6th ed, Oxford University Press, p. 47, 2003.
• [9] J.A. Tropp, ”Random Filters for Compressive Sampling”, Proceedings of 40th Annual Conference on Information Sciences and Systems, pp. 216 - 217, 22-24 March 2006.
• [10] R. DeVore, ”Deterministic Constructions of Compressed Sensing Matrices”, (2007), Preprint.
• [11] E. Candés, http://www.acm.caltech.edu/l1magic/.


text:
Class Notes (838,076)
Mathematics (1,919)
MATH 138 (181)
Lecture

# Math 138 Notes.pdf

23 Pages
379 Views

School
Department
Mathematics
Course
MATH 138
Professor
Rui Bin Qin
Semester
Fall

Description
Fundamental Theorem of Calculus 1. If ( ) ∫ ( ) , then ( ) ( ), where a is an arbitrary constant. 2. ∫ ( ) ( ) ( ), where F is antiderivatives of f, i.e. F’ = f Note: ( ) ( ) ( ) ( ) ( ( )) ( ) ( ( )) ( ) ∫ ( ) ∫ ( ) Substitution Rule If u = g(x) is differentiable and its range I is the domain of a continuous function f, then ∫ [ ( ) ] ( ) ∫ ( ) ( ) ( ) Integration by parts Let u = f(x), v = g(x),∫then ∫ . Trigonometric Substitution Substitution Domain Note √ √ √ Integration of Rational functions Proper rational functions:  ∫ | |  ∫ ( ) ( )( )  ∫  ∫ ( ) Improper rational functions:  ∫ ( ) ∫ ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) Note: We say ( ) ( ) is improper if ( ) ( ), where ( ) ( ) Volume Definition: Let S is a solid between a and b. If the cross sectional area of S is A(x) (continuous), then volume of S is ∑ ( ) (Riemann Sum) ∫ ( ) Sphere: Using Pythagorean Theorem, y is given by √ . Therefore the area of the cross-sectional area A is given by ( ) (√ ) . Then ∫ ( ) ∫ ( ) Approximation of volume: Divide S into n pieces of equal widthby using the planes where the planes are perpendicular to x-axis and through . If we choose sample points in [ ], then we can approximate the i-th slice by ( ) . Adding volumes of these slices, then we will get ∑ ( ) . The approximation becomes more accurate as ∫ ( ) . Washer: inner radius - , outer radius - , height – h Then ( ) Example: Find the volume of the solid obtained by rotating the region bounded by y = x, about y = 2. Solution: , Then ∫ ( ) ( ) ] Wedges: Given a cylinder with radius r and height h, when we cut the cylinder at an angle, a wedge is produced. To find the volume of the wedge, we sum the area of each triangle formed by the wedge. Example: A wedge is cut out of a cylinder of radius 4 units by two planes. The cutting plane intersects the base at an angle of 30° along the diameter. Find the wedge’s volume. Solution: First, ( ) (√ )(√ ) √ ( ) Then, ∫ ( ) √ ∫ ( ) √ Cylindrical Shell: ( ) ( )( ) ̅ ([average circumference]*[height]*[thickness]) Where ̅ ( ) Let S be the solid obtained by rotating ( ) about the y-axis, where ( ) , y = 0, x = a and x=b. Divide [a,b] into intervals [ ] of the length . Let ̅ be the midpoint of[ ]. Then the volume of i-th cylindrical shell is ( ̅) ( ) . Volume of the solid S is ∑ ̅ ( ̅ ∫ ( ) , where is the circumference, f(x) is the height and dx is the thickness. Improper Integrals Definition:  If f(x) is continuous at [ ], then∫ ( ) ∫ ( ) If the limit exists, integral converges. Otherwise, integral diverges.  Similarly, ∫ ( ) ∫ ( ) .  For ∫ ( ) ∫ ( ) ∫ ( ) exist iff both limits exist.  If f(x) is continuous on ( ), then∫ ( ) ∫ ( ) .  Similarly, ∫ ( ) ∫ ( ) .  If f(x) has discontinuity at point x = c, a < c < b, ∫ ( ) ∫ ( ) ∫ ( ) ∫ ( ) ∫ ( ) iff both limits exist. Comparison Theorem: Suppose f and g are continuous with ( ) ( ) , for , 1) If ∫ ( ) is convergent, the∫ ( ) is also convergent. 2) If ∫ ( ) is divergent, the∫ ( ) is also divergent. Differential Equations Definition:  A Differential Equation (D.E.) is an equation that contains an unknown function and its derivatives.  The order of a D.E. is the order of the highest derivatives that occurs in the equation.  A function f(x) is called a solution to a D.E. if the equation is satisfied when y=f(x) and its derivatives are substituted into the equation.  Initial Value Problem (IVP) – Find a solution of a D.E. that satisfy the condition of the form ( ) .  Direction field is a field where each point is associated with direction. Direction Field: Definition:  A field where each point is associated with a distance ( ) at point ( ).  The slope of a solution is ( ). Note: Use maple to plot the direction fields. Alternatively, calculate manually. Separable Equations: ( ) ( ) ∫ ∫ ( ) ( ) ( ) ( ) [ ( ) ] Mixing Problem: Example: A tank contains 20 kg of salt dissolved in 5000Lof water. Input 0.03kg/L at a rateof 25L/min. The solution is well mixed, anddrains from the tank at the same rate. How much salt is left in tank after half an hour? Solution: [Initial concentration] = 0.04kg/L Let y(t) be the amount of salt remains in the tank at time t. ( ) Input: 0.3 x 25 = 0.75 kg/min ( ) Output: kg/min Rate of change: ∫ ∫ Let u=150-y, du = -dy, y = 150+u ∫ | | ( ) Population Model problem: Law of Natural growth: Rate of growth of the population is proportional to the population. Variable – time, t Population – P(t) ( ) ( ) Where ( ) , P(0) is the initial population. Logistic Model: When the maximum capacity is M, then ( ) Other Models: ( ) e.g. ( )( ) First Order Linear Differential Equations: ( ) ( ) ( ) ( ) Integrating factor: I(x) which satisfies I(x)[y’+P(x)y]=I(x)y. Usually, we take ( ) ∫ ( ) [∫ ( ) ]. Sequences: Definition: A list of numbers written in a definite order i.e. We can write a sequence as or where ( ) Harmonic sequence: { } Fibonacci sequence: Limits of sequence: Definition: The ε-definition of limits. | | Definition: Example: Find the limit of the sequence { } . Solution: From observation, . ( ) ( ) | | If we choose , then whenever n>N, we have | | . Bounded sequence: Definition: A sequence is bounded if , where m is the lower bound and M is the upper bound. Theorem: Every convergent sequence is bounded. Some Limits to remember: 1. 2. 3. √ 4. 5. ( ) Theorem: 1. Let f be any function that is continuous at point p, if is a sequence in the domain of f, ( ) ( ). [ ( ) ( )] 2. If ( ) as and a sequence as , then ( ) [ ( ) ( ) ] Proposition: If f is a function s.t. as and is the sequence given by ( ) then . [ ( ) ( ) ] Monotonic sequence:  Increasing sequence , i.e. . If the inequalities are strictly increasing (< instead of ), we say is strictly increasing.  Decreasing sequence , i.e. . If the inequalities are strictly decreasing (> instead of ), we say is strictly decreasing.  A sequence is monotonic when it is either increasing or decreasing. Monotonic sequence theorem: If a sequence is bounded and monotonic, then has a limit, and therefore convergent. For increasing sequence, the supremum is the limit of the sequence. For decreasing sequence, the infemum is the limit of the sequence. Completeness Axiom for ℝ :  If S is a non-empty set of real numbers that has an upper bound M, then S has a least upper bound  Similarly, if m is a lower bound of a non-empty set of real numbers, then it has a greatest lower bound N.  Sup(s) – supremum S is the least upper bound, Inf(s) – infemum S is the greatest lower bound. Series: Definition: Given a series∑ , let denotes the n-th partial sum of the series i.e. ∑ . If the sequence converges, and exists as a real number, then ∑ is convergent. If the sequence diverges, then the series is divergent. Geometric series: ∑ , where r is the common ratio and . The series converges when |r|<1, diverges when | . Harmonic series: ∑ P-series: The p-series is convergent if p>1 and divergent i. Theorem: If the series is convergent, then . Contrapositive: (Test of divergent) If ( ) or , then the series is divergent. Theorem: ∑ ∑ ∑( ) ∑ ∑ Integral Test: Suppose f is (i) positive, (ii) continuous and (iii) decreasing fun), andon[ ( ), then the series is convergent if and only if the improper i∫tegral is convergent, i.e.: 1. ∫ ( ) ∑ . 2. ∫ ( ) ∑ . Note: While using integral test, it is not necessary to start the series or integral at n=1. It is also not necessary that f is always decreasing. As long as f is ultimately decreasing, then the test can be used. Error/Estimates of the remainder: Let ∑ ∑ , Suppose ( ) , where f is continuous, positive and decreasing fand ∑ is convergent. Then ∫ ( ) ∫ ( ) . ∑ ∫ ( ) ∑ ∫ ( ) More Accurate Estimates: Since , and we know that ∫ ( ) ∫ ( ) . Then we have [ ∫ ( ) ] [ ∫ ( ) ]. Choose the mid point of [ ∫ ( ) ]and [ ∫ ( ) ] as estimate. (Smaller error) The Comparison Test: Suppose that ∑ ∑ are series with positive terms, 1. If ∑ is convergent and , then∑ is also convergent. 2. If ∑ is divergent and , then∑ is also divergent. Note: Usually we use two types of series to prove convergence. 1. p-series, , convergent whenp>1, divergent when . 2. Geometric series, ∑ , convergent when |r|<1, divergent when| . Limit Comparison Test: Suppose ∑ ∑ are series with positive terms. If , where c is a finite number, c>0, then either both series converge or both series diverge. Error/Estimating the sum of series ∑ ∑ Suppose ∑ So , then we use to estimate the error bound. Alternating Series Definition A series whose terms are alternatingly positive and negative. Alternating Series Test If the alternating series ( ) satisfies (i) , (ii) , then the series is convergent. Error/Estimating the sum of series Alternating Series Estimation Theorem: If ∑( ) satisfies (i) , (ii) , then| | | | . Absolute convergence Definition  A series ∑ is absolutely convergent if the series ∑| | is convergent.  A series ∑ is conditionally convergent if it is convergent but not absolutely convergent. Theorem If ∑ is absolutely convergent, then ∑ is convergent. (If ∑| | is convergent, then ∑ is convergent.) Ratio & Root Test Ratio Test | |  If L<1, then ∑ is absolutely convergent.  If L>1, then ∑ is divergent.  If L=1, the ratio test is inconclusive. Root Test √ | |  If L<1, then ∑ is absolutely convergent.  If L>1, then ∑ is divergent.  If L=1, the root test is inconclusive. Note: 1. If we see a factorial(!) sign or the series is recursive i.is defined by , then ratio test is useful. 2. If is a term raised to the power of n, then consider root test. 3. If the ratio test is inconclusive i.e. L=1, so is the root test. Power Series Definition Series in the form of ( ) ( ) ( ) , where are coefficients and a is an arbitrary constant. It is called the power series centereor a power series about . Domain of this function f(x) is the set of x for which the power series converges. Power series always converges at . Theorem Given
More Less

Related notes for MATH 138
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.